The complexity class of decision problems that can be solved using an amount of memory that grows polynomially with the size of the input, regardless of how much time the computation takes; believed, though not proven, to be strictly larger than NP.
Facts
Core PrincipleThe set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. 1 Connections
Sources
1. PSPACE, Wikipedia
Lead section, first sentence
PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
In Group: Space, Exponential Time and Probabilistic Classes, Lead
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.