Deterministic Time
Overview
Initial lectures introduce a version of the model of computation that will be used in much of this course — a Turing machine — along with the use of simulations to compare the computational power of different machine models. They also introduce properties of deterministic computation, and deterministic time-complexity classes, that will be used throughout the course.
Reductions are then introduced. While these can be presented using the information about deterministic computation that has been provided so far, these will be used throughout most of the rest of this course.
Quite a bit of this material has already been introduced in the computer science program — notably, in CPSC 351 (or CPSC 313) and CPSC 413. CPSC 511 will provide additional detail and will include more advanced material that is generally not covered in these prerequisite courses.
Lecture #2: Introduction to Turing Machines
Why This is Included
It tends to be easiest to work with simple abstract models of computation when proving results about computability and computational complexity. Different documents about this frequently use different computational models. However, some version of a Turing machine used more often than anything else, and various versions of Turing machines will be used throughout this course.
This lecture introduces the simplest version of deterministic Turing machines that recognize or decide languages, and that compute functions, that will be considered in this course. These “simplest” models will be related to more complicated (and useful) models later on. They will be used in proofs, when it would be correct to do so, in order to keep the proofs as simple as possible.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #3: Multi-Tape Turing Machines and Simulations
Why This is Included
Of course, we do not use single-tape Turing machines (or computers that resemble them) in real computations. Any theory that is developed using single-tape Turing machines will only be relevant if the computational power of a single-tape Turing machine can be related to the computational power of a more realistic model of computation.
Simulations are used to relate the computational power of different models of computation, and these are introduced in this lecture..
This lecture also introduces a version of a multi-tape Turing machine that will be used to define deterministic-time complexity classes in this course — and it provides a simulation that can be used to relate the computational power of a multi-tape Turing machine to that of the simpler kind of Turing machine that was defined in the previous lecture.
Preparatory Reading
- Multi-Tape Turing Machines and Simulations
[ PDF ]
[ Video ]
- Supplement: More about the Proof of Claim #2 [ PDF ]
- Supplement: Multi-Tape Turing Machines That Compute Functions [ PDF ]
- Supplement: On the Complexity of Palindromes [ PDF ]
- Supplement: A Better Simulation [ PDF ]
Lecture Presentation
Finishing Up
Lecture #4: Universal Turing Machines and the Emulation of Computations
Why This is Included
Results concerning the existence, the efficiency, and the languages of universal Turing machines — which receive encodings of other Turing machines as part of their input and (in some way) emululate computations of the encoded machnes — play important roles in both computabiity and computational complexity theory. Provably “hard” problems are often defined using concepts that will be introduced in this lecture, and results established in this lecture will be applied, almost immediately after this, to establish a significant result about relationships between complexity classes.
As for the previous lectures, this lecture begins with a review — since universal Turing machines have, ideally, been introduced in one or more prerequisites for this course. However, a significant part of the lecture material will almost certainly be material that students are seeing for the first time.
Preparatory Reading
- Universal Turing Machines and the Emulation of Computations
[ PDF ]
[ Video ]
- Supplement: A Better Emulation [ PDF ]
- Supplement: A Useful Lemma about Binary Counters [ PDF ]
- Supplement: A Review of the Diagonalization Method [ PDF ]
Lecture Presentation
Finishing Up
Lecture #5: Speedup and Hierarchy Theorems
Why This is Included
This lecture presents a “linear speedup” theorem which helps to explain why complexity classes (for deterministic time) are defined as they are. In particular, this result explains why it is not necessary, or helpful, to be concerned about multiplicative constants in time bounds when complexity classes are defined and used.
The lecture also includes a “hierarchy” theorem, establishing that various complexity classes, defined using time bounds, are provably distinct. Thus the set of problems that can be solved expands, as we increase the time that can be used to solve them.
While this is probably unsurprising, it is not a straightforward consequence of the definitions of these classes. Indeed, a proof is being described, in part, as a reminder that this really is something that needs to be proved! Fortunately, it can be proved using results and proof techniques that have now been discussed.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #6: Reductions — and Polynomial-Time Oracle Reductions
Why This is Included
The “hierarchy theorem”, given in the previous lecture, establishes the existence of computational problems that cannot be solved, deterministically, within given time bounds. However, it is does not really help us to show that a given computational problem cannot be solved efficiently, when we suspect that this is the case.
This lecture introduces the general proof technique, involving reductions, that is used most often, in computational complexity theory, to establish this kind of result.
It it also introduces one kind of “reduction” that can be used to provide evidence that a given problem cannot be solved, deterministically, in polynomial time.
Preparatory Reading
- Reductions — and Polynomial-Time Oracle Reductions
[ PDF ]
[ Video ]
- Supplement: Proofs of Claims [ PDF ]
Lecture Presentation
Finishing Up
Lecture #7: Polynomial-Time Many-One Reductions — and Properties of Reducibilities
Why This is Included
We will soon be dealing with complexity classes that are not known (or even believed) to be closed under polynomial-time oracle reductions. The kind of reductions introduced in this lecture, specifically, polynomial-time many-one reductions, will sometimes be harder to establish then polynomial-time oracle reductions, but have additional closure properties that polynomial-time oracle reductions seem to lack.
One difference between “computability theory” and “computational complexity theory” is that it seems to be easier to prove various properties of “computability classes” than it is for “complexity classes”. Sometimes we only have conjectures of properties, in computational complexity theory, instead of proofs that these properties hold. The concepts of hardness and completeness, introduced in the lecture, can be useful for identifying languages in a larger complexity class, that would not also belong to a smaller one, if the two complexity classes really were different. This is useful information when a separation between these two complexity classes is conjectured but unproved.
Preparatory Reading
- Polynomial-Time Many-One Reductions — and Properties
of Reducibilities
[ PDF ]
[ Video ]
- Supplement: Proof of Claims [ PDF ]
