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
Aki will hold office hours Friday, Nov 20, 4-5pm in SF4306A. (PS 3 is due the following Monday.)
A slightly revised version of PS 3 is posted Nov 16: Some typos are fixed, and in Question 1 it is emphasized that the circuit families need not be uniform, and in Question 4 it is explained that the set I and the relation R of the path system (n,I,R) are given explicitly.
Solutions and Marking Report for PS 2 are now posted below.
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.
ROOM CHANGE Effective Sept 16 the class meets
Mondays BA 2185
Wednesdays BA 2195
Click here for the course information sheet (a .ps file).
See The Status of the P versus NP Problem for Lance Fortnow's recent CACM article.
Lectures: MW 2-3
Tutor: Akitoshi Kawamura
Occasional Tutorials F 2-3, depending on demand.
Instructor:
Stephen Cook
,
email: sacook@cs,
Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: MW 3:15 - 4:00
Or make an appointment, or drop in.
QUESTIONS VIA EMAIL ARE WELCOME.
Text: "Computational Complexity" by Sanjeev Arora and Boaz Barak
Click here for a draft of the book on the web.
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 three to four problem sets
Problem Sets (.ps files)