Actions

Intro::DSPACE

::concepts

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

{{#invoke:Hatnote|hatnote}} {{ safesubst:#invoke:Unsubst||$N=Refimprove |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }}

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm. It is one of the most well-studied complexity measures, because it corresponds so closely to an important real-world resource: the amount of physical computer memory needed to run a given program.


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

Intro
PREVIOUS: IntroNEXT: Complexity classes
<<>>