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.