### Sumários

##### Relativization and its parameters

17 Dezembro 2014, 10:00 • José Félix Gomes da Costa

##### Polynomial Hierarchy II

12 Dezembro 2014, 11:00 • José Félix Gomes da Costa

Structural theorems by means of quantification: NP = \exists P, co-NP = \forall P, \exists \Sigma_k = \Sigma_k, \forall \Pi_k = \Pi_k, \exists \Pi_k = \Sigma_{k+1}, and \forall \Sigma_k = \Pi_{k+1}. Alternation theorem.

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.

##### Polynomial hierarchy I

10 Dezembro 2014, 10:00 • 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.

##### Formalizing probabilistic algorithms with advice words

5 Dezembro 2014, 11:00 • José Félix Gomes da Costa

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

That ZPP = R \cap co-R.

Identification LasVegas = R intersection co-R.

That every set in BPP can be decided in P with most of the advice words with suitable size, i.e. that the following statements are equivalent: (a) A is in BPP, (b) for every polynomial q, there is a set B in P and a polynomial p such that, for every n, within the words of size p(n), there are 2^p(n) ( 1 - (1/2)^q(n) ) correct advices for A, for words of size n.

PP-complete sets: MAJ e #SAT. Proof by reduction of #SAT to MAJ.