CSC 463H: Computational Complexity and Computability
Winter 2019
ANNOUNCEMENTS
-
Marks for Problem Sets 1-3 and the Midterm Exam are accessible on the course's Quercus page.
-
Schedule for the week of April 1-5:
Monday: Tutorial (2-3pm in the usual classroom) going over solutions to Problem Set 4. Office hours take place 3-4pm in BA6214.
Wednesday: Final regular lecture.
Friday: Optional review and question-and-answer session (2-3pm in the usual classroom).
-
There will be office hours on Monday April 8, 3-4pm in BA6214
-
The Final Exam takes place Wednesday April 10, 7-10pm in EM 119 (Emmanuel College).
The exam covers both computability and complexity (Chapters 4,5,7,8 of the textbook).
-
In weeks 10-12, we will cover Chapter 8 on Space Complexity (and parts of Chapter 9, time permitting).
-
Week 9:
Wrap up NP-completeness; discussion of Search and Optimization Problems (read supplementary lecture notes, link below)
-
Weeks 7-8:
Sipser Chapter 7.4-7.5 and supplementary lecture notes on "NP and NP-completeness" (link below)
-
Week 6:
Sipser Chapter 7.1-7.3 (Time Complexity)
-
Week 5:
Sipser Chapter 6.4 (Kolmogorov Complexity)
ASSIGNMENTS (due at the start of lecture or tutorial)
-
Problem Set 1 due Friday January 25
-
Problem Set 2 due Friday February 15
-
Problem Set 3 due Friday March 15
-
Problem Set 4 due Monday April 1
In Question 3, you may use the fact that NL = coNL and show that 2SAT is coNL-complete by giving a reduction PATH ≤L 2SAT.
Lectures: MW 2-3 in Bahen 1200
Tutorial: F 2-3 in Bahen 1200
Instructor:
Benjamin Rossman (ben.rossman@utoronto.ca)
Office hours: M 3-4 in Bahen 6214
Teaching Assistants:
Adrian She (ashe@cs.toronto.edu) and
Evi Micha (emicha@cs.toronto.edu)
Click here for the course information sheet.
Text: "Introduction to the Theory of Computation"
by Michael Sipser (Second or Third Edition). Chapters 3,4,5,7,8, and
part of Chapter 9.
References
- M. Garey and D. Johnson: Computers and Intractability: A Guide to
the Theory of NP-Completeness. Chapters 1-3 especially relevant.
-
Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms
(Second Edition), MIT Press and McGraw-Hill. Chapter 34 on NP-completeness
is the relevant chapter here.
Course Contents
- Computability Theory (5 weeks): Turing machines, Church's Thesis,
decidability and semi-decidability, diagonal arguments,
the Halting Problem and other undecidable problems, reductions,
complete problems.
- Computational Complexity (7 weeks):
The classes P and NP,
polynomial time reducibility, NP-completeness, Cook-Levin Theorem,
various NP-complete problems, intractable problems, log space,
other topics.
Marking Scheme
- 4 assignments worth 10% each (first two assignments due Jan 25 and Feb 15).
Assignments are due at the beginning of tutorial/class,
since solutions will be discussed during the tutorial/class.
- 1 closed-book test worth 20% (March 1 in tutorial)
- Final exam worth 40%
The work you submit must be your own.
You may discuss problems with each other; however,
you should prepare written solutions alone.
Copying assignments is a serious academic offence and will be dealt with
accordingly.
Supplementary Lecture Notes (.pdf files from earlier versions of this course)
Previous Years' Problem Sets (.pdf files)
Previous Years' Midterm Tests