|
|
|
|
|
ExpspaceIn 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 most authors call the resulting class ESPACE.) In terms of DSPACE, -
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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|