Word.ws English Dictionary

EXPSPACE

EXPSPACE proper noun: the set of all decision problems that can be solved by a Turing machine using O(2ᵖ⁽ⁿ⁾) units of memory, where p(n) is a polynomial function of the input size.

Proper noun

EXPSPACE

  1. The set of all decision problems that can be solved by a Turing machine using O(2ᵖ⁽ⁿ⁾) units of memory, where p(n) is a polynomial function of the input size.
    • First, the hierarchy theorems tell us that a Turing machine can decide more languages in EXPSPACE than it can in PSPACE.1997, Michael Sipser, Introduction to the Theory of Computation, Boston, M.A.: PWS Publishing Company, →ISBN, page 313

Questions about EXPSPACE

What does EXPSPACE mean?
EXPSPACE means the set of all decision problems that can be solved by a Turing machine using O(2ᵖ⁽ⁿ⁾) units of memory, where p(n) is a polynomial function of the input size.
What part of speech is EXPSPACE?
EXPSPACE is a proper noun.

Words near EXPSPACE in the dictionary

  1. expropriator
  2. expropriators
  3. expropriatory
  4. exproprioception
  5. exproprioceptive
  6. EXPSPACE
  7. expt
  8. EXPTIME
  9. exptl
  10. expugn
  11. expugnable

Source and license

Adapted from Wiktionary: EXPSPACE (page history and authors). Text available under the Creative Commons Attribution-ShareAlike 4.0 license. Word.ws reformatted the entry and added links. Wiktionary data of 2026-09-02.

Last updated:

Cite this entry: “EXPSPACE.” Word.ws, https://word.ws/expspace. Based on Wiktionary, CC BY-SA 4.0.