Word.ws English Dictionary

PSPACE

PSPACE proper noun: the set of all decision problems that can be solved by a Turing machine using an amount of memory which is a polynomial function of the input size.

Proper noun

PSPACE

  1. The set of all decision problems that can be solved by a Turing machine using an amount of memory which 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 PSPACE

What does PSPACE mean?
PSPACE means the set of all decision problems that can be solved by a Turing machine using an amount of memory which is a polynomial function of the input size.
What part of speech is PSPACE?
PSPACE is a proper noun.

Words near PSPACE in the dictionary

  1. psoroptids
  2. psorosperm
  3. psorosperms
  4. PSOs
  5. PSP
  6. PSPACE
  7. PSPO
  8. PSPOs
  9. PSPs
  10. pspsps
  11. PSR

Source and license

Adapted from Wiktionary: PSPACE (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: “PSPACE.” Word.ws, https://word.ws/pspace. Based on Wiktionary, CC BY-SA 4.0.