Relation with other complexity classes::DSPACE


Space::''n''    ''M''::turing    Mathcal::input    ''x''::machine    DSPACE::''f''    There::classes

Relation with other complexity classes DSPACE is the deterministic counterpart of NSPACE, the class of memory space on a nondeterministic Turing machine. By Savitch's theorem,<ref name=AB86>Arora & Barak (2009) p.86</ref> we have that

<math>\mbox{DSPACE}[s(n)] \subseteq \mbox{NSPACE}[s(n)] \subseteq \mbox{DSPACE}[(s(n))^2].</math>

NTIME is related to DSPACE in the following way. For any time constructible function t(n), we have

<math>\mbox{NTIME}(t(n)) \subseteq \mbox{DSPACE}(t(n))</math>.

DSPACE sections
Intro  Complexity classes  Machine models  Hierarchy Theorem  Relation with other complexity classes  References  External links  

Relation with other complexity classes
PREVIOUS: Hierarchy TheoremNEXT: References