BPP

5 dezembro 2013, 12:30 • José Félix Costa

Classe BPP.

That the sets in BPP can be decided by bounded error polynomial time probabilistic Turing machines with error probability approaching exponentially to 0 as time goes polynomially to infinity.

Boolean closure of BPP.

Is BPP = P ?

Probabilistic fine structure between P and PSPACE

29 novembro 2013, 10:30 • José Félix Costa

Introduction to Monte Carlo and Las Vegas methods. Probabilistic Turing machines.

Class PP.

Proposition: NP included in PP.

Proposition: For every set A in PP, there exists a probabilistic Turing machine that decides A with accepting probability different from 1/2.

Simulation of probabilistic Turing machines by deterministic Turing machines. PP closed under complementation. PP as interpolator of NP, co-NP and PSPACE.

The fifteen years intersection problem: The symmetric difference, the discovery of D^P, the intersection in PP.

Oracle Turing machines

28 novembro 2013, 12:30 • José Félix Costa

Oracle Turing machines. Examples.

Turing reduction in polynomial time. Characterization. Example: MAXCLIQUE <= CLIQUE.

Some results on relative computation. Example theorem: If T is a tally set and DEXT(T) = DEXT, than T \in P.

Equivalence between closure under complementation and closure under Turing reduction for some complexity classes, such like NP and co-NP.

The open problem NP =/= co-NP.

NP- and PSPACE- and NLOG-completeness III

22 novembro 2013, 10:30 • José Félix Costa

NP-completeness of SAT, CNF-SAT and CLIQUE.

Boolean formulas (9/14)

Boolean formulas. Quantified Boolean formulas.

Boolean formulas in conjunctive normal form.

Compactification theorem: If F is a Boolean formula in the variables x_1, ..., x_t, then there exists an equivalent Boolean formula E y1, ... y_m F', constructible in polynomial time, such that the variables y_1, ..., y_m are fresh and F' is in conjunctive normal form.

Sets SAT, CNF-SAT and QBF.

Reduction SAT < CNF-SAT via compactification.

List of some complete problems:

NP : SAT, CNF-SAT, CLIQUE, K.

P: CVP, LIFE_WITHOUT_DEATH.

NLOG : REACHABILITY.

PSPACE : QBF, CSG-ACCEPTANCE.

++++++++++++++++++++

Exercício: 

Converta as seguintes fórmulas booleanas em fórmulas booleanas quantificadas:  (a) não (x e y e 0), (b) não não x e 1 ou não (z ou y), (c) não (não (não (x e não y) ou não não z) e não 0), (d) (x e z) ou (y e não z).

NP- and PSPACE- and NLOG-completeness II

21 novembro 2013, 12:30 • José Félix Costa

PSPACE-completeness of CSG-ACCEPTANCE.

NLOG-completeness of REACHABILITY.