Hierarchy theorems and its implications in structural complexity (part 2)

5 novembro 2021, 08:30 • José Félix Costa

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

Space and time hierarchy theorems.

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