Characterization of P = PSPACE

3 novembro 2017, 10:00 • José Félix Costa

Charaterization of P = PSPACE in terms of functions.

Honest functions.

Lifting

27 outubro 2017, 10:00 • José Félix Costa

Book' technique for sufficient conditions.

NSPACE(n) incl. NP implies NP = PSPACE. Separation NSPACE(n) =/= NP.

DTIME(2^kn) incl. NP implies DEXT incl. NP = PSPACE = EXPTIME. Separation DTIME(2^kn) =/= NP.

Tally sets. 

DEXT =/= EXPSPACE implies there exist tally sets in PSPACE - P.

Savitch' theorem

25 outubro 2017, 16:00 • José Félix Costa

Savitch's theorem.

Diagram of relations between basic classes DTIME(t(n)), DTIME(2^O(t(n))), DSPACE(t(n)), DSPACE(t(n)^2), NTIME(t(n)), NSPACE(t(n)), co-NSPACE(t(n)).

Relations between central complexity classes: LOG, NLOG, co-NLOG, P, DEXT, EXPTIME, NP, PSPACE, NPSPACE, EXPSPACE, NEXT, NEXPTIME.

Hierarchy theorems and its implications in structural complexity

20 outubro 2017, 10:00 • José Félix Costa

Space and time hierarchy theorems.

Complexity Zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo.

Central complexity classes

18 outubro 2017, 16:00 • José Félix Costa

Non-deterministic Turing machines.

Diagram of relations between basic classes DTIME(t(n)), DTIME(2^O(t(n))), DSPACE(t(n)), DSPACE(t(n)^2), NTIME(t(n)), NSPACE(t(n)), co-NSPACE(t(n)).