Sumários
R and ZPP
14 dezembro 2016, 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.
Probabilistic Turing machines
9 dezembro 2016, 11:00 • José Félix Costa
Class PP. Examples of PP algorithms (Monte Carlo).
Structural relations between NP, co-NP, PP and PSPACE. Closure of PP under complementation. 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 polynomially to infinity.
Polynomial Hierarchy II
7 dezembro 2016, 10:00 • José Félix Costa
Polynomial time hierarchy by means of bounded quantification. Alternation theorem.
The collapse of the polynomial hierarchy.
Polynomial hierarchy I
2 dezembro 2016, 11:00 • José Félix Costa
The polynomial hierarchy PH. Collapse theorems.