EXPSPACE

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.) If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by Savitch's theorem.

In terms of DSPACE and NSPACE,

{\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})

A decision problem is 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 problems might be thought of as the hardest problems in EXPSPACE.

EXPSPACE is a strict superset of PSPACE, 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).^[1]

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

↑ Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.

L. Berman The complexity of logical theories, Theoretical Computer Science 11:71-78, 1980.
Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. 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)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX

Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete

Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL

Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy

Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

This article is issued from Wikipedia - version of the 9/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

EXPSPACE

See also

References