Central complexity classes I

15 outubro 2014, 10:00 • José Félix Costa

Upper bound on the number of configurations of a space bounded Turing machine. Decidability of the halting problem of space-bounded Turing machines.

Relation between time and space resources of Turing machines.

Classes DTIME(t) and DSPACE(s), for time and space resources t and s, respectively. Central complexity classes: LOG, P, PSPACE, DEXT, EXPSPACE, EXPTIME. First structural relations.