Sumários

Test 2

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

TEST 2.



Relativization and its parameters

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

Proof of Theorem of Xu, Donner and Book:
 
Let M_1, M_2, ... be an enumeration of non-deterministic oracle Turing machines clocked in a class F of time-constructible bounds. If the two following conditions hold, then there exists an oracle B such that, NTIME(F)(B) is not included in the set {S: S is decided by Turing machine M_i, for some i, with oracle B}:
 
1) For each Turing machine M_i, there exists a function f_i in F such that, for all i, for all oracle A, for all input w, |Q(M_i,A,w)| <= f_i(|w|);
 
2) There exists a function t in F such that, for all f in F, for almost all n, 2^t(n) > f(n).
 
Proof of the separations:
 
2) There exists a decidable set B such that P(B) =/= NP(B);
 
3) There exists a decidable set B such that DEXT(B) =/= NEXT(B);
 
4) There exists an oracle B such that NP_b =/= NP;
 
5) There exists a set in NP(B), for some oracle B, that can not be decided with a polynomial number of queries.
 
 


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.