Nondeterministic Time
Overview
Lectures will continue by introducing nondeterministic Turing machines, as well as “verification”, in order to give a definition of nondeterministic time, and associated computational complexity classes.
While properties of nondeterministic time-complexity classes will be discussed, the focus will be on the use of reductions to better understand the relationship between deterministic time-bounded computation and nondeterministic time-bounded computation. This course will review — and, almost certainly, expand on the information about — the theory of NP-completeness, which students have generally seen before when completing CPSC 413.
Lecture #8: Introduction to Nondeterministic Computation
Why This is Included
As computers became available in the mid-20th century, it became clear that algorithms, which had been used to solve problems by hand, were not always efficient enough to remain useful. Asymptotically efficient algorithms for these problems, to replace these algorithms, were not always discovered.
These were often problems requiring a search for a structure that was defined by a problem’s input, which satisfied a given set of properties.
For some of these problems the related problem, of checking whether a given structure satisfied the required properties, seemed to be much easier: An asymptotically efficient algorithm for this problem was easy to find.
Returning to the orignal problem, this suggested an efficient “nondeterministic” process in which one could guess a structure and then deterministically verify that it satisfied the properties that were required.
This lecture provides a formal introduction to both of the notions of “nondeterministic computation” that have now been informally described. It relates the completexity classes that are defined using each idea, and it states quite a bit of what is known about the relationship between deterministic complexity classes and nondeterministic complexity classes. Thus, it sets things up for a complexity-theoretic study of nondeterministic computation.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #9: Nondeterministic Time — Speedup, Emulation, and a Nondeterministic Time Hierarchy Theorem
Why This is Included
Quite a bit of the material in this lecture is not included (or, sometimes, even mentioned) in other undergraduate courses in computational complexity theory. It is included, in this course, because it can be helpful to understand that, in many ways, nondeterministic time complexity classes have the same properties that determnistic time complexity classes do.
Some of the results and proofs, given here, might be surprising. For example, one might not expect that an asymptotically more efficient simulation of a multi-tape nondeterministic Turing machine, by a three-tape nondeterministic Turing machine, can be described. One might also be surprised to realize that diagonalization cannot be used, directly, to establish a “Nondeterministic Time Hierarchy Theorem” — but you can still establish this kind of a result (and, furthermore, a somewhat stronger result can be established) anyway.
The material is included because it is (arguably) interesting, somewhat surprising, and because an examination of this material might help to better understand the power — and limits — of nondeterminism, as well as the power, and limits, of at least one of the proof techniques that are regularly used.
Preparatory Reading
- Nondeterministic Time — Speedup, Emulation, and a
Nondeterministic Time Hierarchy Theorem
[ PDF ]
[ Video ]
- Supplement: Proof of the Nondeterministic Time Hierarchy Theorem [ PDF ]
Lecture Presentation
Finishing Up
Lecture #10: Nondeterministic Time — More about NP, and co-NP
Why This is Included
As previous lectures should suggest, polynomial-time oracle reductions and polynomial-time many-one reductions can be introduced, without discussing nondeterminism at all. However, since virtually every language in the complexity class “P” is complete for “P”, with respect to these reductions, it is not clear (when you do this) that these reductions can be used to prove anything of interest.
This situation changes — or, at least, can change — as soon as the complexity class “NP” and Cook’s conjecture that P ≠ NP, are introduced. The material at the beginning of this lecture is intended to show this. A process to establish that a language is not in P, if P ≠ NP, is described — and some evidence that this process might be useful is given.
The notes also introduce a related computational complexity class, “co-NP”, along with statements of properties of this complexity class. This class is of interest because there are considerably many languages (with associated computational problems) that belong to co-NP, but are not presently known to belong to P. The notions of “co-NP hardness” and “co-NP completeness” are useful, for many of the reasons why the notions of “NP hardness” and “NP completeness” are.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #11: The Cook-Levin Theorem
Why This is Included
While the previous lecture introduce an NP-complete language, this language is so closely tied to nondeterministic computation — and, in a way, so artificial — that it is not clear that it is helpful: There is no apparent way to use this to prove other languages are NP-complete too.
This lecture outlines a proof of “The Cook-Levin Theorem” — establishing that a considerably more natural language (and associated decision problem), concerning the satisfiability of Boolean formulas, is also NP-complete.
This has been considered to be an extremely important result since the time it was established: It makes a major step toward establishing that “the theory of NP-completeness” really is useful.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #12: NP-Completeness — Classical Reductions
Why This is Included
The identification of a single reasonably “natural” NP-complete language was certainly encouraging. Several other NP-complete languages — involving computational problems in several areas — were identified shortly after this. This supplied further evidence that it might feasible to prove the NP-completeness of a language.
Several of the earliest proofs of the NP-completness of languages are included in these notes, along with information that can be used to discover considerably more NP-complete languages, as well.
Note that — even with only a handful of NP-complete languages having identified at this point — it was already getting easier to choose “an NP-complete language that you already know about” that allows a reasonably simple reduction to be given, in order to establish the NP-completeness of another language. That being noted: While the polynomial-time many-one reductions in these notes are worth studying, students should not be surprised if the reductions that they need to give, in order to solve problems on assignments and tests, are simpler than these!
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #13: What If...? More about Nondeterministic Computation
Why This is Included
Researchers have been trying, now, to prove that P ≠ NP, for almost one half-century. Other researchers have been trying to prove that P = NP, instead, for the same amount of time. A variety of results about the implications of either answer for this question have been established, together with results that eliminate strategies for answering it..
The proofs of the results make use of “padding” and a technique that involves “self-reduction” which may be of interest — even though the proofs are too long, and too complicated, for students to be expected to examine them in any detail or to explain them. The results concerning “intermediate” languages, and the “collapse” of complexity classes (and complexity hierachies) may suggest interesting things about how computational complexity “behaves”.
Preparatory Reading
- What If...? More about Nondeterministic Computation
[ PDF ]
[ Video ]
- Supplement: If P ≠ NP Then NP-Intermediate Languages Exist [ PDF ]
- Supplement: More about Relativization and Relativized Proofs [ PDF ]
Lecture Presentation
Finishing Up
Lecture #14: Beyond NP — Introduction to the Polynomial Hierarchy
Why This is Included
A consideration of the problems like the “k-Clique” problems may suggest related decision problems that do not seem to be in either NP or co-NP. For example, when given an undirected graph G and a positive integer k, we might ask whether the largest clique in G has size k.
A consideration of these problems leads to the definition of a hierarchy of complexity classes, called “The Polynomial Hierarchy”, that has P, NP and co-NP at the bottom.
While this hierarchy is not especially natural” or interesting by itself, it turns out that various conjectures about the Polynomial Hiearchy imply other things about computational complexity, and the resources needed to solve problems, that are probably more interesting — and the Polynomial Hierarchy continues to be remembered, and discussed, because of that.
