Editing Space complexity

{{Short description|Computer memory needed by an algorithm}}
The '''space complexity''' of an [[algorithm]] or a [[data structure]] is the amount of memory space required to solve an instance of the [[computational problem]] as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely.<ref>{{citation|title=Optimal Reliability Modeling: Principles and Applications|first1=Way|last1=Kuo|first2=Ming J.|last2=Zuo|publisher=John Wiley & Sons|year=2003|isbn=9780471275459|url=https://books.google.com/books?id=vdZ4Bm-LnHMC&pg=PA62|page=62}}</ref> This includes the memory space used by its inputs, called '''input space''', and any other (auxiliary) memory it uses during execution, which is called '''auxiliary space'''.

Similar to [[time complexity]], space complexity is often expressed asymptotically in [[big O notation|big ''O'' notation]], such as <math>O(n),</math>
<math>O(n\log n),</math> <math>O(n^\alpha),</math> <math>O(2^n),</math> etc., where {{mvar|n}} is a characteristic of the input influencing space complexity.

==Space complexity classes==

Analogously to time complexity classes [[DTIME|DTIME(f(n))]] and [[NTIME|NTIME(f(n))]], the complexity classes [[DSPACE|DSPACE(f(n))]] and [[NSPACE|NSPACE(f(n))]] are the sets of languages that are decidable by deterministic (respectively, non-deterministic) [[Turing machine]]s that use <math>O(f(n))</math> space. The complexity classes [[PSPACE]] and [[NPSPACE]] allow <math>f</math> to be any polynomial, analogously to [[P (complexity)|P]] and [[NP (complexity)|NP]].  That is,
<math display=block>\mathsf{PSPACE} = \bigcup_{c \in \Z^+} \mathsf{DSPACE}(n^c)</math>
and
<math display=block>\mathsf{NPSPACE} = \bigcup_{c \in \Z^+} \mathsf{NSPACE}(n^c)</math>

==Relationships between classes==

The [[space hierarchy theorem]] states that, for all [[space-constructible function]]s <math>f(n),</math> there exists a problem that can be solved by a machine with <math>f(n)</math> memory space, but cannot be solved by a machine with asymptotically less than <math>f(n)</math> space.

The following containments between complexity classes hold.<ref>{{citation |title=Computational Complexity : A Modern Approach |edition=draft|year=2007|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|isbn=9780511804090 |page=76 |url=https://theory.cs.princeton.edu/complexity/book.pdf}}</ref>
<math display=block>\mathsf{DTIME}(f(n)) \subseteq \mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n)) \subseteq \mathsf{DTIME}\left(2^{O(f(n))}\right)</math>

Furthermore, [[Savitch's theorem]] gives the reverse containment that if <math>f \in \Omega(\log(n)),</math>
<math display=block>\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}\left((f(n))^2\right).</math>

As a direct corollary, <math>\mathsf{PSPACE} = \mathsf{NPSPACE}.</math> This result is surprising because it suggests that non-determinism can reduce the space necessary to solve a problem only by a small amount. In contrast, the [[exponential time hypothesis]] conjectures that for time complexity, there can be an exponential gap between deterministic and non-deterministic complexity.

The [[Immerman–Szelepcsényi theorem]] states that, again for <math>f\in\Omega(\log(n)),</math> <math>\mathsf{NSPACE}(f(n))</math> is closed under complementation. This shows another qualitative difference between time and space complexity classes, as nondeterministic time complexity classes are not believed to be closed under complementation; for instance, it is conjectured that NP ≠ [[co-NP]].<ref>{{citation
 | last = Immerman | first = Neil | authorlink = Neil Immerman
 | doi = 10.1137/0217058
 | issue = 5
 | journal = SIAM Journal on Computing
 | mr = 961049
 | pages = 935–938
 | title = Nondeterministic space is closed under complementation
 | url = http://www.cs.umass.edu/~immerman/pub/space.pdf
 | volume = 17
 | year = 1988}}</ref><ref>{{citation
 | last = Szelepcsényi | first = Róbert | author-link = Róbert Szelepcsényi
 | journal = Bulletin of the EATCS
 | pages = 96–100
 | title = The method of forcing for nondeterministic automata
 | volume = 33
 | year = 1987}}</ref>

==LOGSPACE==
{{main|L (complexity)}}

L or LOGSPACE is the set of problems that can be solved by a deterministic Turing machine using only <math>O(\log n)</math> memory space with regards to input size. Even a single counter that can index the entire <math>n</math>-bit input requires <math>\log n</math> space, so LOGSPACE algorithms can maintain only a constant number of counters or other variables of similar bit complexity.

LOGSPACE and other sub-linear space complexity is useful when processing large data that cannot fit into a computer's [[Random access memory|RAM]]. They are related to [[Streaming algorithm]]s, but only restrict how much memory can be used, while streaming algorithms have further constraints on how the input is fed into the algorithm.
This class also sees use in the field of [[pseudorandomness]] and [[derandomization]], where researchers consider the open problem of whether [[L (complexity)|L]] = [[RL (complexity)|RL]].<ref>{{citation
 | last = Nisan | first = Noam | author-link = Noam Nisan
 | contribution = RL ⊆ SC
 | doi = 10.1145/129712.129772
 | location = Victoria, British Columbia, Canada
 | pages = 619–623
 | title = Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92)
 | year = 1992| isbn = 0-89791-511-9 | s2cid = 11651375 }}.</ref><ref>{{citation
 | last1 = Reingold | first1 = Omer | author1-link = Omer Reingold
 | last2 = Trevisan | first2 = Luca | author2-link = Luca Trevisan
 | last3 = Vadhan | first3 = Salil | author3-link = Salil Vadhan
 | contribution = Pseudorandom walks on regular digraphs and the RL vs. L problem
 | contribution-url = http://people.seas.harvard.edu/~salil/research/regular.pdf
 | doi = 10.1145/1132516.1132583
 | mr = 2277171
 | pages = 457–466
 | publisher = ACM | location = New York
 | title = STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing
 | year = 2006| isbn = 1-59593-134-1 | s2cid = 17360260 }}</ref>

The corresponding nondeterministic space complexity class is [[NL (complexity)|NL]].

==Auxiliary space complexity==

The term '''{{visible anchor|auxiliary space}}''' refers to space other than that consumed by the input.
Auxiliary space complexity could be formally defined in terms of a [[Turing machine]] with a separate ''input tape'' which cannot be written to, only read, and a conventional working tape which can be written to.
The auxiliary space complexity is then defined (and analyzed) via the working tape.
For example, consider the [[depth-first search]] of a [[Binary tree#Types of binary trees|balanced binary tree]] with <math>n</math> nodes: its auxiliary space complexity is <math>\Theta(\log n).</math>

==See also==

* {{annotated link|Analysis of algorithms}}
* {{annotated link|Computational complexity theory}}
* {{annotated link|Computational resource}}

==References==

{{reflist}}

[[Category:Computational complexity theory]]
[[Category:Computational resources]]