# 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

• 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

## Assignments

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)

Midterm Guide
Midterm

## 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 1 (Jan 6-10)
Topics: Introduction to the course, finite automata and regular languages

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
• 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)
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)

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)

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