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

3 Novembro 2021, 16:00 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.