Matches in DBpedia 2014 for { <http://dbpedia.org/resource/EXPSPACE> ?p ?o. }
Showing items 1 to 30 of
30
with 100 items per page.
- EXPSPACE abstract "In 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 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,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).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.".
- EXPSPACE wikiPageID "54703".
- EXPSPACE wikiPageRevisionID "540801595".
- EXPSPACE hasPhotoCollection EXPSPACE.
- EXPSPACE subject Category:Complexity_classes.
- EXPSPACE type Abstraction100002137.
- EXPSPACE type Class107997703.
- EXPSPACE type Collection107951464.
- EXPSPACE type ComplexityClasses.
- EXPSPACE type Group100031264.
- EXPSPACE comment "In 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.".
- EXPSPACE label "EXPSPACE".
- EXPSPACE label "EXPSPACE".
- EXPSPACE label "EXPSPACE".
- EXPSPACE label "EXPSPACE".
- EXPSPACE label "EXPSPACE".
- EXPSPACE label "EXPSPACE".
- EXPSPACE label "EXPSPACE".
- EXPSPACE sameAs EXPSPACE.
- EXPSPACE sameAs EXPSPACE.
- EXPSPACE sameAs EXPSPACE.
- EXPSPACE sameAs EXPSPACE.
- EXPSPACE sameAs EXPSPACE.
- EXPSPACE sameAs EXPSPACE.
- EXPSPACE sameAs m.0f8c5.
- EXPSPACE sameAs Q1141985.
- EXPSPACE sameAs Q1141985.
- EXPSPACE sameAs EXPSPACE.
- EXPSPACE wasDerivedFrom EXPSPACE?oldid=540801595.
- EXPSPACE isPrimaryTopicOf EXPSPACE.