Sumários
NP- and PSPACE- and NLOG-completeness I
14 novembro 2013, 12:30 • José Félix Costa
NP-completeness of K, SAT, CNF-SAT and CLIQUE. PSPACE-completeness of QBF. NLOG-completeness of REACHABILITY.
Context sensitive grammars. Theorem: the class of sets generable by context sensitive grammars is NSPACE(n). Consequences.
PSPACE-completeness of CSG-ACCEPTANCE.
Tally sets
8 novembro 2013, 10:30 • José Félix Costa
Theorem. DEXT =/= NEXT iff there exist tally sets in NP - P.
Theorem. EXPSPACE =/= DEXT iff there exist tally sets in PSPACE - P.
Consequences of those two theorems.
Exercise:
Mostre que A in NP sse existem um conjunto B in P e um polinómio p tais que x in A sse existe y, |y| <= p(|x|), <x,y> in B.
Reduction (technique)
7 novembro 2013, 12:30 • José Félix Costa
Reduction.
Hard and complete sets for a class of sets. The semi-lattice of polinomial degres. Least upper bounds. Characterization of P in terms of m-reduction.
Application of m-reduction to the solution of conjectures P = NP and NP = co-NP.
Proof of the separation PSPACE =/= DEXT through m-reduction.
Exercises:
Mostre que:
(a) Se A se reduz a B, então A reduz-se a B;
(b) Se A é C-difícil e A se reduz a B, então B é também C-difícil;
(c) Se A é C-completo, A reduz-se a B e B está em C, então B é também C-completo;
(d) Se A é C-difícil, então A é co-C-difícil;
(e) Se C é fechado para a complementação, então se A é C-difícil, também A é C-difícil;
(f) As classes P, NP, co-NP, PSPACE estão fechadas para a redução.
Lifting through padding (technique)
1 novembro 2013, 10:30 • José Félix Costa
NSPACE(n) incl. NP implies NP = PSPACE;
Separation NSPACE(n) =/= NP;
P = PSPACE implies DTIME(f^O(1)) = DSPACE(f^O(1)), for time constructible superpolinomial f;
P = PSPACE implies DTIME(2^O(f)) = DSPACE(2^O(f)), for time constructible f;
DSPACE(n) incl. P implies P = PSPACE;
Separation DSPACE(n) =/= P;
P = NP implies DTIME(2^O(f)) = NTIME(2^O(f)), for time constructible f;
P = NP implies DEXT = NEXT;
NLOG incl. LOG implies DSPACE(f) = NSPACE(f), for space constructible f, such that f(n) >= log(n);
DTIME(2^kn) incl. NP implies DEXT incl. NP = PSPACE = EXPTIME;
Separation DTIME(2^kn) =/= NP.