R and ZPP

13 Dezembro 2017, 16:00 José Félix Gomes da 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.

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

Class ZPP. That ZPP = R \cap co-R.

Monte Carlo vs. Las Vegas.