Now we turn to computations that can be performed in a given amount of memory. Memory is usually called space.
Definition. PSPACE is the class of all problems that can be solved by a (deterministic) algorithm using space limited by nk for some fixed k.
An example of a problem in PSPACE is the satisfiability problem. You can solve SAT by trying every possible assignment of values to the variables. That takes a lot of time, but not much space.
Think of a truth-value assignment as a sequence of 0's and 1's, where 0 indicates false and 1 indicates true. If there are v variables, then there are v bits in the sequence.
But a sequence of bits is just a binary number. You can try all assignments by starting with 0 and adding 1 each time around a loop, since adding 1 moves to the next collection of values to try.
Since SAT is in PSPACE and SAT is NP-complete, every problem in NP is in PSPACE. That is,
Theorem. NP ⊆ PSPACE.
PSPACE is defined in terms of deterministic algorithms. So it is closed under complementation. Consequently,
Theorem. coNP ⊆ PSPACE.
It appears that PSPACE is a large class that contains some difficult problems. But nobody knows how to prove that.
Conjecture. NP ≠ PSPACE.
Conjecture. P ≠ PSPACE.
If you want to prove that P ≠ NP, you might warm up by showing that P ≠ PSPACE.