Sumários

TEST

18 Dezembro 2015, 11:00 José Félix Gomes da Costa

Test. (Test 2 of 2.)



Relativization

16 Dezembro 2015, 10:00 José Félix Gomes da 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 Gomes da 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 Gomes da 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 Gomes da 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.