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.