CAS 776: Computability and Complexity
Fall 2002
- Instructor: Michael Soltys, email:
my last name at mcmaster.ca
- Course Information
- Course outline: Introduction to computability
and complexity: problems, algorithms, and languages. Turing machines,
recursive and recursively enumerable languages, the Halting Problem,
and Rice's theorem. Determinism and non-determinism in computations.
Complexity classes defined in terms of time, space, boolean formulas
and circuits. The diagonalization method (in showing problems
undecidable, and in the time (and space) hierarchy). The reachability
method (Savitch's theorem, and the Immerman-Szelepscenyi theorem).
The P versus NP problem, reductions and completeness. Randomized and
parallel computations. NP and co-NP, and propositional proof systems.
- Textbook:
"Computational Complexity", by
Christos H. Papadimitriou , and here is the
errata , and the book cover:
- Check this web page regularly for announcements. Some documents
will be available in PostScript; if you need a PostScript previewer,
go to Ghostview Software.
Announcements:
- Nov 15: Solutions to Assignment 3 have been posted below.
- Nov 11: Assignment 4 (the last one!) has been posted below.
- Oct 31: Remember that next week we have an extra class on Friday;
that is, we have a class on Thursday Nov 7 as usual, PLUS a class on
Friday Nov 8, from 9:30 until 11:20 in room 225.
- Oct 28: Assignment 3 has been posted below.
- Oct 9: Assignment 2 has been posted below.
- Old Announcements
Assignments: