Sumários
Relativization
16 dezembro 2015, 10:00 • José Félix Costa
Positive relativizations.
Negative relativizations: Theorem of Xu, Donner and Book.
Proof that there exists a set in NP(B), for some oracle B, that can not be decided with a polynomial number of queries.
R
11 dezembro 2015, 11: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.
Problems addressed:
1) Whether P = R;
2) Whether R = NP;
Proof (by padding and self-reducibility of SAT) that if NP is included in BPP, then NP = R.
BPP
9 dezembro 2015, 10:00 • José Félix Costa
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.
Boolean closure of BPP.
Probabilistic Turing machines
4 dezembro 2015, 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.