Sumários
Characterization P = NP
16 novembro 2018, 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.
Lifting
14 novembro 2018, 16:00 • José Félix Costa
Book' technique for sufficient conditions.
DSPACE(n) incl. P implies P = PSPACE. Separation DSPACE(n) =/= P.
DTIME(2^kn) incl. NP implies DEXT incl. NP = PSPACE = EXPTIME. Separation DTIME(2^kn) =/= NP.
Tally sets. EXPSPACE =/= DEXT iff there exist tally sets in PSPACE - P.
Savitch' theorem
9 novembro 2018, 10:00 • José Félix Costa
Savitch's theorem.
Relations between central complexity classes: LOG, NLOG, co-NLOG, P, DEXT, EXPTIME, NP, PSPACE, NPSPACE, EXPSPACE, NEXT, NEXPTIME.