Probabilistic Turing machines

6 dezembro 2017, 16:00 • José Félix Costa

Class PP. Structural relations between NP, co-NP, PP and PSPACE. Closure of PP under complement. The intersection problem in PP.

Classe BPP. Proof hat the sets in BPP can be decided by bounded error polynomial time probabilistic Turing machines with error probability exponentially approaching 0 as time goes polynomialy to infinity.

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 polynomialy to infinity.

Examples of R algorithms (Monte Carlo).