Encyclopedia > EXPSPACE

  Article Content

EXPSPACE

In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) space, where p(n) is a polynomial function of n.

Some authors restrict p(n) to be a linear function, but a more common definition is to allow p(n) to be any polynomial.

The complexity class EXPSPACE-complete is also a set of decision problems. A decision problem is in EXPSPACE-complete if it is in EXPSPACE, and every problem in EXPSPACE has a many-one reduction[?] to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. EXPSPACE-complete might be thought of as the hardest problems in EXPSPACE.

EXPSPACE is a strict superset of EXPTIME, PSPACE, NP-complete, NP, and P.

An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions are limited to four operators: union, concatenation, the Kleene star (zero or more copies of an expression), and squaring (two copies of an expression).

If the Kleene star is left out, then that problem becomes NEXPTIME-complete, which is like EXPTIME-complete, except it is defined in terms of non-deterministic Turing machines rather than deterministic.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
David McReynolds

... a three-way split in 1973. The SPA was renamed the Social Democrats USA by the right-wing leadership (neo-conservatives). Michael Harrington and his followers ...

 
 
 
This page was created in 40.5 ms