CSC 2401F: Introduction to Computational Complexity
Fall, 2011

Announcements

Marker's Comments and Solutions to PS4 posted below.

Lectures: M 3-4 in BA 2175 and F 3-4 in BA2179
Tutorials: W 3-4 in BA 2175

Tutor: Dustin Wehr

Instructor: Stephen Cook , email: sacook@cs, Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: Monday 4:15 - 5:00, Wednesday 4:30 - 5:30 Or make an appointment, or drop in.
QUESTIONS VIA EMAIL ARE WELCOME.

Text: "Computational Complexity" by Sanjeev Arora and Boaz Barak
The course will cover roughly Chapters 1 - 7, and parts of Chapters 14, 17 and possibly other topics.

Click here for Allan Borodin's Lecture Note on computational complexity. Lectures 17 - 20 on Boolean circuit complexity and Alternating Turing Machines are especially relevant.

Click here for old lecture notes on "Turing Machines and Reductions". Of special interest for this course are pages 8-10 describing search problems and polynomial time Turing reductions (i.e. `Cook reductions').

References:
Michael Sipser: Introduction to the Theory of Computation
[More Elementary -- Chapter 7 is a good source for NP-completeness]

Christos Papadimitriou: Computational Complexity

Ding-Zhu Du and Ker-I Ko: Theory of Computational Complexity

Michael Garey and David Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. [A classic reference giving hundreds of NP-complete problems.]

Marking Scheme: Marks will be based on four problem sets.

Problem Sets (.ps files)

Click here for last year's web site for CSC 2401, including problem sets.