CSC 463: Computational Complexity and Computability

Winter 2020

Welcome to the course. This page will be used to share files related to the course. As of June 7, solutions have been removed from the website to preserve academic integrity. However, other materials will remain in case it is helpful to students.

Course Outline

As of March 25, the course marking scheme has been changed due to the cancellation of in-person final exams this semester. Your course mark will be computed based on the maximum of two possible schemes, where


Problem Set 1 (due January 31 on Crowdmark)
Problem Set 2 (due Feburary 14 on Crowdmark)
Problem Set 3 (due March 13 on Crowdmark)
Problem Set 4 (due April 2 on Crowdmark)
Problem Set 5 (due April 17 on Crowdmark)

Exam Material

Midterm Guide

Supplementary Notes

Turing Machines and Reductions
Computability and Noncomputability
CFLs and Noncomputability
NP and NP Completeness
Search and Optimization Problems

Tutorial Sheets

Tutorial 1
Tutorial 2
Tutorial 3
Tutorial 4

Week-by-Week Outline and Readings

Week 1 (Jan 6-10)
Topics: Introduction to the course, finite automata and regular languages
Reading: Sipser Chapter 1

Week 2 (Jan 13-17)
Topics: Turing machines, Church-Turing thesis, equivalence between different models for Turing machines (multi-tape TMs, nondeterministic TMs, enumerators)
Reading: Sipser Chapter 3, Page 1-3 of Turing Machines and Reductions

Turing Machine Simulation

Week 3 (Jan 20-24)
Topics: Decidable and undecidable problems: diagonalization arguments to prove undecidability, using reductions to prove undecidability
Reading: Sipser Chapter 4.2, 5.1 (skip Reductions via Computational Histories), 5.3, Computability and Noncomputability notes (skip Lemma 1 and Pages 11-13)

Week 4 (Jan 27-31)
Topics: Further examples of undecidable problems: Rice's Theorem, Post Correspondence Problem
Reading: Sipser Chapter 5 (skip Def 5.6-Theorem 5.13 in Reductions via Computational Histories), Computability and Noncomputability notes (skip Lemma 1 and Pages 11-13)

Week 5 (Feb 3-7)
Topics: Further examples of undecidable problems: problems related to context-free grammars, Kolmogorov complexity
Reading: Sipser 2.1 (up to Definition 2.7 of ambiguity), Sipser Chapter 6.4
Optional Readings: CFLs and Noncomputability notes, Sipser Chapter 6.2

Our coverage of Kolmogorov complexity in class was slightly different from the material covered in Sipser. We talked about Prof. Luca Trevisan's notes on Kolmogorov complexity more or less covers what we did in class.

Week 6 (Feb 10-14)
Topics: Basics of time complexity theory: defining P, NP, and NP-completeness
Reading: Sipser 7.1-7.4 (up to Theorem 7.36). Most of this material should be covered in classes like CSC 373 that most students in this class have already taken, so feel free to skim the sections rather than doing a close reading. The most important sections are "Complexity Relationships among Models" in Section 7.1, Theorem 7.20 in Section 7.3 (equivalence between definitions of NP), and Section 7.4 (definition and properties of NP-Complete problems).
Optional Reading: Theorem 9.10 in Sipser 9.1 (Proof of the Time Hierarchy Theorem)

Reading Week (Feb 17-21)
Office hours for midterm preparation in BA 2283 on Tuesday, Feb 18 and Thursday, Feb 20 between 2-4pm.

Week 7 (Feb 24-28)
Topics: NP-Complete Problems and Reductions (Monday/Friday), Midterm Exam (Wednesday)
Reading: Sipser 7.4-7.5

In class we presented a sequence of polynomial-time reductions: SAT -> 3SAT -> CLIQUE -> INDEPENDENT-SET -> VERTEX-COVER and the Cook-Levin theorem establishes that each of these problems is NP-Complete.

Proof of the Cook Levin Theorem Slides
Images from the slides taken Karp's Reducibility among Combinatorial Problems", Abtruse Goose, and xkcd.

Week 8 (Mar 2-6)
Topics: Additional Examples of NP-Complete problems: graph colouring, Hamiltonian path, travelling salesperson problem
Reading: Sipser 7.5 (up to Theorem 7.55)
Optional Reading: NP-Completeness of Subset Sum (Sipser Theorem 7.56), supplementary notes on NP Completeness and NP-hard search problems by Steve Cook, Sipser 10.1 (Approximation Algorithms)

Here are some notes on the NP-completeness of Hamiltonian path.

Here is also a website from the University of Waterloo about solving the travelling salesperson problem. The best known approximation algorithm for Metric-TSP in terms of its approximation ratio is Christofides algorithm and improving it has been an open problem in the area of approximation algorithms.

Week 9 (Mar 9-13)
Topics: Space complexity: Savitch's Theorem, PSPACE and PSPACE-Completeness
Reading: Sipser 8.1-8.3
Optional Reading: Sipser 9.1 (proof of the Space Hierarchy Theorem)

Rest of the Term
Since in person classes have been cancelled due to the ongoing COVID-19 pandemic, classes will transition to online. See the class Piazza for more details. We will try to finish the following topics:

Additional Resources

The CSC 463 Website from Winter 2019 includes problem sets and midterms from previous years.
The Engineering and Computer Science Library in the Sandford Fleming building has copies of Sipser available for short term loan for students in this course.
Other references for interested individuals : Blogs about theoretical computer science for those interested in TCS research: