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.

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

**Scheme 1:**18% each Problem Sets 1-4, 28% midterm**Scheme 2:**12.5% each Problem Sets 1-4, 25% Problem Set 5, 25% midterm

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)

Midterm

Computability and Noncomputability

CFLs and Noncomputability

NP and NP Completeness

Search and Optimization Problems

Tutorial 2

Tutorial 3

Tutorial 4

__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

__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

- Definition of Kolmogorov complexity of a string and basic properties
- Examples of compressible strings (digits of pi, repetitive strings). These have Kolmogorov complexity O(log n) where n is the length of the string, rather than O(n) for incompressible strings.
- Proof that testing a string is incompressible or not is undecidable, although with high probability a random string is incompressible
- Statement of Chaitin's Incompleteness Theorem (without proof)

__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.

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:

- PSPACE-Completeness (Sipser 8.3)
- Logarithmic space computation and NL-Completeness (Sipser 8.4-8.6)
- NL-Completeness Slides
- Brief overview of current frontiers in complexity theory and end of course review (parts of Sipser Chapter 9-10)
- Final Lecture Slides
- Playlist for all Lecture Videos

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 :

- Computational Complexity: A Modern Approach by Arora and Barak
- Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson
- Computational Complexity: A Conceptual Perspective by Goldreich
- Computational Complexity by Papadimitriou
- The Complexity Zoo Wiki