R and ZPP

21 dezembro 2018, 10: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.

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.