R

11 dezembro 2015, 11:00 • José Félix Costa

Class R.

Proof that the sets in R can be decided by bounded error polynomial time probabilistic Turing machines with error probability (for probabilistic accepted words) approaching exponentially to 0 as time goes polynomially to infinity.

Problems addressed:

1) Whether P = R;

2) Whether R = NP;

Proof (by padding and self-reducibility of SAT) that if NP is included in BPP, then NP = R.