Sumários

R and ZPP

21 Dezembro 2018, 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

19 Dezembro 2018, 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.



Assessment

14 Dezembro 2018, 10:00 José Félix Costa

ASSESSMENT 2.


Polynomial time hierarchy

12 Dezembro 2018, 16:00 José Félix Costa

The polynomial time hierarchy. 

Polynomial time hierarchy by means of bounded quantification. Alternation.


Polynomial time hierarchy

7 Dezembro 2018, 10:00 José Félix Costa

The polynomial hierarchy. 

Polynomial time hierarchy by means of bounded quantification.

Collapse theorems.