Sumários
R and ZPP
13 dezembro 2017, 16: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
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).
Polynomial Hierarchy
29 novembro 2017, 16:00 • José Félix Costa
The polynomial hierarchy.
Polynomial time hierarchy by means of bounded quantification. Alternation theorem.
Collapse theorems.
Oracle Turing machines
24 novembro 2017, 10:00 • José Félix Costa
Turing reduction in polynomial time. Characterization. Example: MAXCLIQUE <= CLIQUE.
Some results on relative computation. Example theorem: If T is a tally set and DEXT(T) = DEXT, than T \in P.
Equivalence between closure under complementation and closure under Turing reduction for some complexity classes, such like NP and co-NP.
The open problem NP =/= co-NP.