GetWiki
EXPSPACE
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
EXPSPACE
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{Short description|Set of decision problems}}{{Technical|date=January 2024}}In computational complexity theory, {{Sans-serif|EXPSPACE}} is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., 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 {{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.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}}.- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
Formal definition
In terms of {{Sans-serif|DSPACE}} and {{Sans-serif|NSPACE}},
mathsf{EXPSPACE} = bigcup_{kinmathbb{N}} mathsf{DSPACE}left(2^{n^k}right) = bigcup_{kinmathbb{N}} mathsf{NSPACE}left(2^{n^k}right)
Examples of problems
{{anchor|EXPSPACE-complete}}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).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.If the Kleene star is left out, then that problem becomes {{Sans-serif|NEXPTIME-complete}},{{citation needed|date=August 2021}} 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.JOURNAL, Alur, Rajeev, Henzinger, Thomas A., 1994-01-01, A Really Temporal Logic, J. ACM, 41, 1, 181â203, 10.1145/174644.174651, 0004-5411, free, The coverability problem for Petri Nets is {{Sans-serif|EXPSPACE}}-complete.JOURNAL,
author = Charles Rackoff, The covering and boundedness problems for vector addition systems, Theoretical Computer Science, 223â231, 1978,
The reachability problem for Petri nets was known to be {{Sans-serif|EXPSPACE}}-hard for a long time,JOURNAL, Lipton, R.,citeseer.ist.psu.edu/contextsummary/115623/0, The Reachability Problem Requires Exponential Space, Technical Report 62, Yale University, 1976, but shown to be nonelementary,CONFERENCE, Wojciech CzerwiÅski SÅawomir Lasota Ranko S LaziÄ Jérôme Leroux Filip Mazowieckibook-title = STOC 19 | EXPSPACE}}. In 2022 it was shown to be Ackermann function | -complete.LEROUX | CHAPTER=THE REACHABILITY PROBLEM FOR PETRI NETS IS NOT PRIMITIVE RECURSIVE | TITLE=2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) | PUBLISHER=IEEE | DOI=10.1109/FOCS52979.2021.00121 | ARXIV=2104.12695, BRUBAKER >FIRST=BEN | TITLE=AN EASY-SOUNDING PROBLEM YIELDS NUMBERS TOO BIG FOR OUR UNIVERSE | WEBSITE=QUANTA MAGAZINE, Relationship to other classes{{Sans-serif|EXPSPACE}} is known to be a strict superset of {{Sans-serif|PSPACE}}, {{Sans-serif|NP}}, and {{Sans-serif|P}}. It is further suspected to be a strict superset of {{Sans-serif|EXPTIME}}, however this is not known.See alsoReferences
|
- content above as imported from Wikipedia
- "EXPSPACE" does not exist on GetWiki (yet)
- time: 7:47am EDT - Wed, May 22 2024
- "EXPSPACE" does not exist on GetWiki (yet)
- time: 7:47am EDT - Wed, May 22 2024
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 21 MAY 2024
The Illusion of Choice
Culture
Culture
GETWIKI 09 JUL 2019
Eastern Philosophy
History of Philosophy
History of Philosophy
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
© 2024 M.R.M. PARROTT | ALL RIGHTS RESERVED