Sumários

Test 2

19 dezembro 2014, 11:00 José Félix Costa

TEST 2.



Relativization and its parameters

17 dezembro 2014, 10:00 José Félix 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 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.