Sumários

TESTE 2

20 Dezembro 2013, 10:30 José Félix Gomes da Costa

TESTE 2

 


Polynomial hierarchy

19 Dezembro 2013, 12:30 José Félix Gomes da Costa

The polynomial hierarchy PH.

Structural theorems by means of machines. That PH \subseteq PSPACE.

Structural theorems by means of quantification. That NP = \exits P and co-NP = \forall P.

The collapse of the polynomial hierarchy: (a) that \Pi_k = \Sigma_k for some k>0, implies the collapse of PH and (b) that PH = PSPACE implies the collapse of PH.

That BPP = \Sigma_k \cap \Pi_k.

 


ZPP

13 Dezembro 2013, 10:30 José Félix Gomes da Costa

Class ZPP.

That for ZPP we can start with a small percentage of accepting/rejecting computations.

Boolean closure of ZPP.

That P \subseteq R \cap co-R \subseteq NP \cap co-NP.

That ZPP = R \cap co-R.

Formalizing probabilistic algorithms with advice words. That every set in BPP can be decided in P with most of the advice words with suitable size. That every set in PP can be decided in P with more than a half of the advice words with suitable size.

 


R

12 Dezembro 2013, 12:30 José Félix Gomes da Costa

Class R. Examples of POL in R.

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.

Closure of R under union and intersection.

Problems addressed:

1) Whether P = R;

2) Whether R = NP;

The main theorem: If NP is included in BPP, then NP = R. Proof by padding and self-reducibility of SAT.

 


Não houve aula

6 Dezembro 2013, 10:30 José Félix Gomes da Costa

O docente não deu a aula em virtude do seu envolvimento na conferência internacional Philosophy of Science in the 21st Century.