Sumários
Complete sets for PP
23 maio 2013, 10:30 • José Félix Costa
Non-deterministic Turing machines as Boolean formulas: The Boolean formula ACCEPT(w)(x_1,...,x_n).
PP-complete sets: MAJ e #SAT. Proof by reduction of #SAT to MAJ.
Probabilistic interpolates of P included in NP
17 maio 2013, 11:30 • José Félix Costa
Class R. Examples of POL and PROD in R.
Problems addressed:
1) Whether P = R;
2) Whether R = NP;
The main theorem: If NP is included in BPP, then NP = R. Proof by padding and self-reducibility of SAT.
Identification LasVegas = R intersection co-R.
Intersection in PP
16 maio 2013, 10:30 • José Félix Costa
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 open problem with intersection in PP: The symmetric difference, the discovery of D^P, the intersection in PP.
BPP.
That 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.
Is BPP = P ?
Consequences of NP included in BPP.
Probabilistic fine structure between P and PSPACE
10 maio 2013, 11:30 • José Félix Costa
Introduction to Monte Carlo and Las Vegas methods. Examples: polynomial identity, matrix multiplication, minimum cut of graphs.
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.