Space-Bounded Computation
Space-bounded computations and complexity classes will now be considered.
Computations that can be carried out using an amount of work space that is bounded by a polynomial function of the length of the input string, and the complexity class PSPACE, will be considered. Relationships between time-bounded and space-bounded complexity classes will be established, a complete problem for PSPACE will be identified, and the relationship between deterministic and nondeterministic space-bounded computation will be considered.
We will also go inside the complexity class P by considering computations using work space that is bounded by a function that is logarithmic in the length of the input string, instead, as well as associated reductions and complexity classes. A new kind of reducibility is needed for interesting results to be established, and this will be introduced, so that complete problems can be introduced here too. Another interesting result (and different) result about nondeterminnistic computation at this level will also be described.
