Polynomial space
From Wikipedia, the free encyclopedia
In computational complexity theory, polynomial space refers to the space required in computation of a problem where the space, m(n), is no greater than a polynomial function of the problem size, n.
Written mathematically, m(n) = O(nk) where k is a constant (which may depend on the problem).
The complexity class of decision problems that can be solved on a deterministic sequential machine in polynomial time is known as PSPACE. The class of decision problems that can be verified in polynomial space is known as NPSPACE. Equivalently, NPSPACE is the class of decision problems that can be solved in polynomial space on a non-deterministic Turing machine (NPSPACE stands for Nondeterministic Polynomial space).
By Savitch's theorem, PSPACE = NPSPACE.
