Sumários
Karp reduction
14 novembro 2014, 11:00 • José Félix Costa
Hard and complete sets for a class of sets.
Discussion of m-reduction in the context of conjectures P =/= NP and NP =/= co-NP.
Proof of the separation PSPACE =/= DEXT through m-reduction argument.
NP-completeness of K.
Context sensitive grammars. That the class of sets generable by context sensitive grammars is NSPACE(n).
PSPACE-completeness of CSG-ACC.
Lifting through padding (technique)
12 novembro 2014, 10:00 • José Félix Costa
That NSPACE(n) incl. NP implies NP = PSPACE;
Separation NSPACE(n) =/= NP;
That DTIME(2^kn) incl. NP implies DEXT incl. NP = PSPACE = EXPTIME;
Separation DTIME(2^kn) =/= NP.
That DEXT =/= NEXT iff there exist tally sets in NP - P.
Characterization of P = NP
7 novembro 2014, 11:00 • José Félix Costa
Honest functions.
Characterization of NP in terms of functions: a set is in NP iff it is the range of an honest function computable in polynomial time.
Characterization of P = NP: The structural relation P = NP holds iff ANY honest functions computable in polinomial time has ONE INVERSE computable in polinomial time.
Characterization of P = PSPACE
31 outubro 2014, 11:00 • José Félix Costa
Characterization of P in terms of functions: a set is in P iff it is the range of a function computable in polynomial time with an inverse computable in polinomial time.
Charaterization of P = PSPACE in terms of function classes.