Space-Bounded Computation
Complex complications can fail because their completion would require more storage space than is available — and space-bounded computations are important, just as time-bounded computations are.
The study of this, in this course, will initially focus on 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 on the associated complexity class, PSPACE. 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 nondeterministic computation at this level will also be described.
Lecture #15: Space-Bounded Computations — PSPACE
Why This is Included:
Once again, “one has to start somewhere”. If you are carefully examining the work space needed for a computation — especially when you are trying to show that not much work space is really needed — then it arguably makes sense not to include the space needed to store the computation’s input or its output — because this space is unavoidable.
In this set of lecture notes, the definition of a “Turing machine” is adjusted, so that space-bounded computations can be more easily studied. It is checked that this change to the model of computation does not significantly effect the complexity classes (defined using it) that have been introduced already. The new complexity class that will (initially) be most intensively studied — PSPACE — is introduced and related to the time-bounded complexity classes that have been studied, so far.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #16: PSPACE = NPSPACE
Why This is Included:
This presents a major result “Savitch’s Theorem”, establishing that introducing nondeterminism does not significantly reduce the amount of work space needed to decide membership in languages. The proof is reasonably simple (although it is certainly not trivial), and studying it may help students to see how bounds on the space, needed for computations, can be established.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #17: A PSPACE-Complete Problem
Why This is Included
If reductions, and the notions of “hardness” and “completeness” are to be applied, to better understand space-bounded computations, then it is necessary to identify a kind of “reduction” for which PSPACE is provably closed, and to identify a PSPACE-complete language. These things are accomplished in this lecture.
Preparatory Reading
- A PSPACE-Complete Problem:
[ PDF ]
[ Video ]
- Supplement: Proofs of Claims [ PDF ]
- Supplement: Additional PSPACE-Complete Problems [ PDF ]
Lecture Presentation
Finishing Up
Lecture #18: More about Alternation
Why This is Included
As previously noted, various conjectures about the Polynomial Hierarchy imply other things about the resources needed to solve problems using other more interesting (and naturally arising) models of computation.
Some of the studies now carried out, for space-bounded computations, can be extended to better understand alternation and the Polynomial Hierarchy. As shown in these notes, a surprising (and, somewhat interesting) connection between time-bounded computation and space-bounded computation can be established when alternation is also considered.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #19: L, NL, and Log-Space Reducibility
Why This is Included
Computations frequently fail because they need more work space than is available, so problems that can be solved using small amounts of work space — sublinear, and even only logarithmic in the size of the input — are of interest.
Once again, nondeterministic computations can also be considered — and, even though it can be used to show that PSPACE = NPSPACE, Savitch’s Theorem cannot be used to answer all the questions, concerning nondeterminism and low-space computations, that might arise.
It has already been noted that “polynomial-time many-one reductions” are not very useful when consider complexity classes that are subspaces of P. Polynomial-time oracle reductions will not be usful either, so a new kind of reduction must be introduced if reductions, hardness and completeness are going to be used here.
This lecture starts things off by introducing complexity classes to be studied, relating them to complexity classes that have already been considered, and introducing a new kind of reduction that will be used to continue the study of space-bounded computations.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #20: NL = co-NL
Why This is Included
The notes for this lecture begin by establishing that a language, corresponding to the problem of discover whether one vertex is reachable from another one in a directed graph, is hard for NL with respect to log-space many-one reductions. Thus it supplies a first NL-complete language, allowing log-space reductions to be used to establish the NL-hardness of other languages as well.
Since complexity hierarchies do not generally “collapse downward”, the fact that PSPACE = NPSPACE does not necessarily imply that L = NL as well — and, indeed, this is not generally believed to be true. The fact that NL = co-NL — established at the end of the notes for this lecture — is somewhat surprising and is, arguably interesting in its own right. The proof (which takes advantage of a property of the “PATH” problem) is somewhat interesting too.
