### 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.