Computational Complexity studies the amount of resources (time, memory, random bits, etc) needed to solve computational problems. It is of central importance in Computer Science, having spawned the notion of NP-completeness, modern cryptography, and important algorithms.
This is a 'Foundations Course', and is intended to appeal both to theory students and nontheory students.
Announcements
Hints for PS 4:
-- 3b): This is tricky. The idea is to start by dividing the
number of input 1's by a. Try solving this for the special case
a=b=2. If you can do that, then you can solve the general case.
--For Question 4, note that INT-PERM cannot be in #P, because it can take on negative values. You should solve this problem directly from the definition of #P (as opposed to using fancy reductions in the text or tutorial).
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 the course information sheet (a .ps file).
Lectures: M 3-4 in WB130 and W 3-4 in BA1240
Tutorials: F 3-4 in BA3004
Tutor: Kaveh Ghasemloo
Instructor:
Stephen Cook
,
email: sacook@cs,
Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: MW 4:15 - 5:00
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.
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)