CSC 463H: Computational Complexity and Computability
Winter 2019
ANNOUNCEMENTS

Marks for Problem Sets 13 and the Midterm Exam are accessible on the course's Quercus page.

Schedule for the week of April 15:
Monday: Tutorial (23pm in the usual classroom) going over solutions to Problem Set 4. Office hours take place 34pm in BA6214.
Wednesday: Final regular lecture.
Friday: Optional review and questionandanswer session (23pm in the usual classroom).

There will be office hours on Monday April 8, 34pm in BA6214

The Final Exam takes place Wednesday April 10, 710pm in EM 119 (Emmanuel College).
The exam covers both computability and complexity (Chapters 4,5,7,8 of the textbook).

In weeks 1012, we will cover Chapter 8 on Space Complexity (and parts of Chapter 9, time permitting).

Week 9:
Wrap up NPcompleteness; discussion of Search and Optimization Problems (read supplementary lecture notes, link below)

Weeks 78:
Sipser Chapter 7.47.5 and supplementary lecture notes on "NP and NPcompleteness" (link below)

Week 6:
Sipser Chapter 7.17.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 coNLcomplete by giving a reduction PATH ≤_{L} 2SAT.
Lectures: MW 23 in Bahen 1200
Tutorial: F 23 in Bahen 1200
Instructor:
Benjamin Rossman (ben.rossman@utoronto.ca)
Office hours: M 34 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 NPCompleteness. Chapters 13 especially relevant.

Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms
(Second Edition), MIT Press and McGrawHill. Chapter 34 on NPcompleteness
is the relevant chapter here.
Course Contents
 Computability Theory (5 weeks): Turing machines, Church's Thesis,
decidability and semidecidability, diagonal arguments,
the Halting Problem and other undecidable problems, reductions,
complete problems.
 Computational Complexity (7 weeks):
The classes P and NP,
polynomial time reducibility, NPcompleteness, CookLevin Theorem,
various NPcomplete 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 closedbook 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