PSPACE

P3S1P3A1C3E1

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.

UncommonScrabble 12
Ask AI about this wordChatGPTClaudePerplexityGoogle AIGrok

Meanings

proper noun
  1. computingThe 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
Cite this entry
APA

PSPACE. (n.d.). In WatkinsX Dictionary. Retrieved November 2, 2026, from https://dictionary.watkinsx.com/word/PSPACE

MLA

“PSPACE.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/PSPACE. Accessed November 2, 2026.

Chicago

WatkinsX Dictionary, s.v. “PSPACE,” accessed November 2, 2026, https://dictionary.watkinsx.com/word/PSPACE.

Source: PSPACE on Wiktionary, CC BY-SA 4.0.