World Library  
Flag as Inappropriate
Email this Article

Dspace

Article Id: WHEBN0000658520
Reproduction Date:

Title: Dspace  
Author: World Heritage Encyclopedia
Language: English
Subject: World Oral Literature Project, NSPACE, Dspace, EXPSPACE, NTIME
Collection: Complexity Classes, Computational Resources
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Dspace

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.

Contents

  • Complexity classes 1
  • Machine models 2
  • Hierarchy Theorem 3
  • Relation with other complexity classes 4
  • References 5
  • External links 6

Complexity classes

The measure DSPACE is used to define complexity classes, sets of all of the decision problems which can be solved using a certain amount of memory space. For each function f(n), there is a complexity class SPACE(f(n)), the set of decision problems which can be solved by a deterministic Turing machine using space O(f(n)). There is no restriction on the amount of computation time which can be used, though there may be restrictions on some other complexity measures (like alternation).

Several important complexity classes are defined in terms of DSPACE. These include:

  • REG = DSPACE(O(1)), where REG is the class of regular languages. In fact, REG = DSPACE(o(log log n)) (that is, Ω(log log n) space is required to recognize any non-regular language).[1] [2]

Proof: Suppose that there exists a non-regular language LDSPACE(s(n)), for s(n) = o(log log n). Let M be a Turing machine deciding L in space s(n). By our assumption MDSPACE(O(1)); thus, for any arbitrary k\mathbb{N}, there exists an input of M requiring more space than k.

Let x be an input of smallest size, denoted by n, that requires more space than k, and \mathcal{C} be the set of all configurations of M on input x. Because MDSPACE(s(n)), then |\mathcal{C}| \le 2^{c.s(n)} = o(log n), where c is a constant depending on M.

Let S denote the set of all possible crossing sequences of M on x. Note that the length of a crossing sequence of M on x is at most |\mathcal{C}|: if it is longer than that, then some configuration will repeat, and M will go into an infinite loop. There are also at most |\mathcal{C}| possibilities for every element of a crossing sequence, so the number of different crossing sequences of M on x is

|S|\le|\mathcal{C}|^{|\mathcal{C}|} \le (2^{c.s(n)})^{2^{c.s(n)}}= 2^{c.s(n).2^{c.s(n)}}< 2^{2^{2c.s(n)}}=2^{2^{o(\log \log n)}} = o(n)

According to pigeonhole principle, there exist indexes i < j such that \mathcal{C}_i(x)=\mathcal{C}_j(x), where \mathcal{C}_i(x) and \mathcal{C}_j(x) are the crossing sequences at boundary i and j, respectively.

Let x' be the string obtained from x by removing all cells from i + 1 to j. The machine M still behaves exactly the same way on input x' as on input x, so it need the same space to compute x' as to compute x. However, |x' | < |x|, contradicting the definition of x. Hence, there does not exist such language L as the assumption. □

The above theorem implies the necessity of space-constructible function assumption in the space hierarchy theorem.

  • L = DSPACE(O(log n))
  • PSPACE = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(n^k)
  • EXPSPACE = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k})

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.

Hierarchy Theorem

The space hierarchy theorem shows that, for every space-constructible function f: \mathbb{N} \to \mathbb{N}, there exists some language L which is decidable in space O(f(n)) but not in space o(f(n)).

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,[3] we have that

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

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

\mbox{NTIME}(t(n)) \subseteq \mbox{DSPACE}(t(n)).

References

  1. ^ Szepietowski (1994) p.28
  2. ^ Alberts, Maris (1985), Space complexity of alternating Turing machines 
  3. ^ Arora & Barak (2009) p.86
  • Szepietowski, Andrzej (1994). Turing Machines with Sublogarithmic Space.  
  •  

External links

Complexity Zoo: ))n(fDSPACE(.

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.