Sumários
Relativization and its parameters
17 dezembro 2014, 10:00 • José Félix Costa
Polynomial Hierarchy II
12 dezembro 2014, 11:00 • José Félix 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 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 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.