PSPACE is the class of decision problems solvable by a deterministic Turing machine using an amount of working storage bounded by a polynomial in the input length (Wayne 2005). The running time need not be bounded by a polynomial.
A decision problem is PSPACE-complete when it belongs to PSPACE and every problem in PSPACE can be transformed to it by a polynomial time many-one reduction. Such a reduction maps an input to a single new input with the same yes-or-no answer.
