“EXPSPACE”的意思、由来-开放百科全书

词条

EXPSPACE

释义

Examples of problems
See also
References

In complexity theory, '{{Sans-serif|EXPSPACE}}' is the set of all decision problems solvable by a deterministic Turing machine in space, where is a polynomial function of . (Some authors restrict to be a linear function, but most authors instead call the resulting class {{Sans-serif|ESPACE}}.) If we use a nondeterministic machine instead, we get the class {{Sans-serif|NEXPSPACE}}, which is equal to {{Sans-serif|EXPSPACE}} by Savitch's theorem.

In terms of {{Sans-serif|DSPACE}} and {{Sans-serif|NSPACE}},

A decision problem is {{Sans-serif|EXPSPACE-complete}} if it is in {{Sans-serif|EXPSPACE}}, and every problem in {{Sans-serif|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. {{Sans-serif|EXPSPACE-complete}} problems might be thought of as the hardest problems in {{Sans-serif|EXPSPACE}}.

{{Sans-serif|EXPSPACE}} is a strict superset of {{Sans-serif|PSPACE}}, {{Sans-serif|NP}}, and {{Sans-serif|P}} and is believed to be a strict superset of {{Sans-serif|EXPTIME}}.

Examples of problems

An example of an {{Sans-serif|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 {{Sans-serif|NEXPTIME-complete}}, which is like {{Sans-serif|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 {{Sans-serif|EXPSPACE}}.

Alur and Henzinger extended Linear temporal logic with times (integer) and prove that the validity problem of their logic is EXPSPACE-complete^[2].

The reachability problem for Petri Nets is EXPSPACE-hard. ^[3]

References

1. ^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.
2. ^{{Cite journal|last=Alur|first=Rajeev|last2=Henzinger|first2=Thomas A.|date=1994-01-01|title=A Really Temporal Logic|url=http://doi.acm.org/10.1145/174644.174651|journal=J. ACM|volume=41|issue=1|pages=181–203|doi=10.1145/174644.174651|issn=0004-5411}}
3. ^{{cite journal | last = Lipton | first = R. | url = http://citeseer.ist.psu.edu/contextsummary/115623/0 | title = The Reachability Problem Requires Exponential Space | journal = Technical Report 62 | publisher = Yale University | date = 1976 }}

L. Berman The complexity of logical theories, Theoretical Computer Science 11:71-78, 1980.
{{cite book|author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = 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.

1 : Complexity classes

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Examples of problems

See also

References