Space::''n'' ''M''::turing Mathcal::input ''x''::machine DSPACE::''f'' There::classes
Machine models DSPACE is traditionally measured on a deterministic Turing machine. Several important space complexity classes are sublinear, that is, smaller than the size of the input. Thus, "charging" the algorithm for the size of the input, or for the size of the output, would not truly capture the memory space used. This is solved by defining the multi-string Turing machine with input and output, which is a standard multi-tape Turing machine, except that the input tape may never be written-to, and the output tape may never be read from. This allows smaller space classes, such as L (logarithmic space), to be defined in terms of the amount of space used by all of the work tapes (excluding the special input and output tapes).
Since many symbols might be packed into one by taking a suitable power of the alphabet, for all c ≥ 1 and f such that f(n) ≥ 1, the class of languages recognizable in c f(n) space is the same as the class of languages recognizable in f(n) space. This justifies usage of big O notation in the definition.
Intro Complexity classes Machine models Hierarchy Theorem Relation with other complexity classes References External links
|PREVIOUS: Complexity classes||NEXT: Hierarchy Theorem|