EXPSPACE

The Television & Movie Wiki: for TV, celebrities, and movies.

In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2^p(n)) space, where p(n) is a polynomial function of n. (Some authors restrict p(n) to be a linear function, but most authors instead call the resulting class ESPACE.)

In terms of DSPACE,

<math>\mbox{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k})</math>

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 polynomial-time 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 PSPACE, NP-complete, NP, and P and is believed to be a strict superset of EXPTIME.

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.

It has also been shown by L. Berman in 1980 that the problem of verifying / falsifying any first-order statement about real numbers that involves only addition and comparison (but no multiplication) is in EXPSPACE.

References

• L. Berman The complexity of logical theories, Theoretical Computer Science 11:71-78, 1980.
• {{qif

 |test={{{Authorlink|}}}
 |then={{wikilink
   |1={{{Authorlink}}}
   |2={{qif
     |test={{{Author|}}}
     |then=Michael Sipser
     |else={{{Last|}}}{{qif
       |test={{{First|}}}
       |then=, {{{First}}}
     }}
   }}
 }}
 |else={{qif
   |test={{{Author|}}}
   |then=Michael Sipser
   |else={{{Last|}}}{{qif
     |test={{{First|}}}
     |then=, {{{First}}}
   }}
 }}

}}{{qif

 |test={{{Coauthors|}}}
 |then=, {{{Coauthors}}}

}}{{qif

 |test={{{Date|}}}
 |then= ({{{Date}}})
 |else={{qif
   |test={{{Year|}}}
   |then={{qif
     |test={{{Month|}}}
     |then= ({{{Month}}} 1997)
     |else= (1997)
   }}
 }}

}}{{qif

 |test={{{Author|{{{Last|{{{Year|}}}}}}}}}
 |then=.

}}{{qif

 |test={{{Chapter|}}}
 |then= "{{{Chapter}}}"

}}{{qif

 |test={{{Editor|}}}
 |then= {{{Editor}}}

}} {{qif

 |test={{{URL|}}}
 |then=[{{{URL}}} Introduction to the Theory of Computation]
 |else=Introduction to the Theory of Computation

}}{{qif

 |test={{{Others|}}}
 |then=, {{{Others}}}

}}{{qif

 |test={{{Edition|}}}
 |then=, {{{Edition}}}

}}{{qif

 |test={{{Pages|}}}
 |then=, {{{Pages}}}

}}{{qif

 |test={{{Publisher|}}}
 |then=, {{qif
   |test={{{Location|}}}
   |then={{{Location}}}: 
 }}PWS Publishing

}}{{qif

 |test={{{ID|}}}
 |then=. ISBN 0-534-94728-X

}}. Section 9.1.1: Exponential space completeness, pp.313–317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete.

Important complexity classes (more)

P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C

EXPTIME | EXPSPACE | PR | RE | Co-RE | RE-C | Co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH

es:EXPSPACE