Sumários
Uniform diagonalization
22 novembro 2017, 16:00 • José Félix Costa
Recursively presentable computational classes. P(A) for a decidable A, P, PSPACE, NP, NP-complete, co-NP, co-NP-complete, and PSPACE-complete.
Uniform diagonalization and its applications (Ladner's theorem and other results). Negative results for recursively presentability. NP - P, NP - NP-complete, P - FIN.
NP-completeness
17 novembro 2017, 10:00 • José Félix Costa
Boolean formulas. Quantified Boolean formulas.
NP-completeness of SAT, F-SAT, CNF-SAT, CLIQUE and VERTEX-COVER.
PSPACE-completeness of QBF.
NP- and PSPACE-complete sets
15 novembro 2017, 16:00 • José Félix Costa
Many to one reduction in polynomial time. Hard and complete sets.
Proof of the separation PSPACE =/= DEXT through a 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.
Characterization P = NP
10 novembro 2017, 10: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.
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 EVERY honest function computable in polinomial time has one inverse computable in polinomial time.
Applications to Cryptography.