Sumários
Polynomial hierarchy
19 dezembro 2013, 12:30 • José Félix 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 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 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 Costa
O docente não deu a aula em virtude do seu envolvimento na conferência internacional Philosophy of Science in the 21st Century.