CMPT 308
Computability & Complexity  Summer 2019
Announcements
 Aug 2: I'll have 2hour office hours on Wed, Aug 7, 11:3013:30.
 Aug 2: The final exam on Aug 8 will be on all topics of the course, with equal emphasis. You'll have 3 hours for an exam that will be roughly two quizzes in size. To prepare, go over all lecture slides and notes, HWs, quizzes, and the textbook. The questions on the final exam will be similar to those on the quizzes we had.
 July 30: Quiz 4 solutions are posted.
older announcements...
 July 25: Quiz 4 will cover lectures 1927 (inclusive).
 July 21: The soutions to HW 4 are now posted.
 July 14: Quiz 3 solutions are now posted.
 July 4: No classes on Wed, July 10, and Fri, July 12, as I'm away at a conference.
 July 1: Quiz 3 will cover the material from Lectures 1218 (inclusive).
 June 20: There will be no class on Wed, June 26 (as I'll be away).
 June 16: Quiz 2 will cover the material from lectures 712, excluding the Recursion Theorem. That is, Quiz 2 will cover TMs, decidability, undecidability, nonsemidecidability, Rice's Theorem, and reductions.
 June 16: The solutions to HW 2 are now posted.
 May 24: Quiz 1 will cover the material from Lectures 16 (inclusive), that is, Regular Languages, their properties, as well as the Pumping Lemma. The problems on the quiz will be similar to those in HW 1.
 May 16: HW 1 is now available.
Course description
This course focuses on the inherent ''complexity'' of solving problems using a computer. The goal is to understand why some seemingly simple problems cannot be solved on computers and others have no efficient (i.e., fast) solution. Formal notions of computers, computability and complexity will be given. At the successful completion of this course, students will understand why, for example, computer viruses are so pervasive and why no one will ever write a perfect virus checker. We will see how these concepts are related to logic, in particular, the famous Incompleteness Theorem of Gödel. Finally, we will see a few surprising results from modern complexity, in particular, the results making use of randomness in computation.
 Topics
 Texts
 Lectures
 Office hours
 Marking scheme
 Models of Computation: Finite automata and Turing machines
 Decidable and undecidable problems
 Recursion theorem
 Kolmogorov complexity
 Gödel's Incompleteness theorems
 NPcompleteness
 Time & Space complexity
 Randomized computation
 Interactive proofs
 Probabilistically Checkable Proofs and the PCP Theorem
 Time & Space Hierarchy Theorems
 Cryptography
 Introduction to the Theory of Computation by Michael Sipser, 2012, 9781133187790; the earlier (second) edition of the book is also OK. [main]
 Introduction to Automata Theory, Languages and Computation  3rd Edition by J.E. Hopcroft , Rajeev Motwani, J.D. Ullman, Addison Wesley, 2006, 9780321455369. [optional]
day  time  room 

Mon  13:3014:20  WMC 3260 
Wed  13:3014:20  WMC 3260 
Fri  13:3014:20  WMC 3260 
 4 inclass 50min quizzes, worth 15% each, and
 final exam, worth 40%
Teaching staff
Instructor: Valentine Kabanets (kabanets@cs.sfu.ca), Office: TASC1 8011
TAs: Fatemeh Hasiri (fhasiri@sfu.ca) and Young Shin Oh (sophieo@sfu.ca)
If you have gradingrelated questions, please email the TAs and ask for an appointment. If you still have questions after meeting with the TA, then come and see me.
Important dates
The 50minute quizzes will be given during our regular lecture times on the following dates.
Quiz 1  Quiz 2  Quiz 3  Quiz 4 

June 3  June 24  July 8  July 29 
Final exam: Thu, Aug 8, 15:3018:30, AQ 3159
Assignments
I'll post homework assignments & solutions.
 Homework 1 solutions
 quiz 1 solutions
 Homework 2 solutions
 quiz 2 solutions
 Homework 3 solutions
 quiz 3 solutions
 Homework 4 solutions
 quiz 4 solutions
Lecture notes
I'll post my lecture notes for each class, and a reading assignment.
 05/6: Lecture 1 (intro, existence of unsolvable problems, Turing machine) Read: Chap. 0, Secs. 4.1, 3.1. (Read ahead: Sec. 1.1.)
 05/10: Lecture 2 (Finite Automata) Read: Sec. 1.1. (Read ahead: Secs. 1.2, 1.3.)
 05/13: Lecture 3 (Regular operations)
 05/15: Lecture 4 (NFA, equivalence of NFA and DFA, regular expressions) Read: Secs. 1.2, 1.3, 1.4. (Read ahead: Secs. 4.1, 3.13.3.)
 05/17: Lecture 5 (regular expressions vs NFA, Pumping Lemma)
 05/22: Lecture 6 (Summary of Regular Languages) Read: Secs. 1.4, 4.1. (Read ahead: Sec. 3.13.3.)
 05/24: Lecture 7 (Turing machines) Read: Sec. 3.2. (Read ahead: Sec. 4.2.)
 05/27: Lecture 8 (Undecidability) Read: Sec. 4.14.2. (Read ahead: Secs. 5.15.3)
 05/29: Lecture 9 (Variants of the Halting problem, reductions)
 05/31: Lecture 10 (reductions) Read: Sec. 5.1 (see the solution to problem 5.28), 5.3. (Read ahead: Secs. 6.1 and 6.2.)
 06/5: Lecture 11 (Rice's Theorem) Read: Secs. 5.3, 6.1. (Read ahead: Secs. 6.4, 6.2.)
 06/7: Lecture 12 (Recursion Theorem)
 06/10: Lecture 13 (Recursion Theorem: Applications)
 06/12: Lecture 14 (Kolmogorov complexity) Read: Sec. 6.4. (Read ahead: Sec. 6.2.)
 06/14: Lecture 15 (Gödel's Incompleteness theorem: Computabilitybased proof) Read: Secs. 6.2, 6.4.
 06/17: Lecture 16 (Towards Gödel's Second Incompleteness Theorem, and Tarski's Theorem) Read: the lecture notes. (Read ahead: Secs. 7.17.4.)
 06/19: Lecture 17 (Gödel's Second Incompleteness Theorem, and Tarski's Theorem)
 06/21: Lecture 18 (Henkin's sentence "I'm provable")
 06/28: Lecture 19 (Complexity Theory: P, NP, and "search to decision" reductions) Read: Secs. 7.17.3. (Read ahead: Sec. 7.4.)
 07/3: Lecture 20 (NPcompleteness) Read: Sec. 7.4. (Read ahead: Sec. 7..)
 07/5: Lecture 21 (CookLevin's Theorem) Read: Sec. 7.4. (Read ahead: Sec. 7.5.)
 07/15: Lecture 22 (NPcomplete versions of SAT) Read: Sec. 7.4. (Read ahead: Sec. 7.5.)
 07/17: Lecture 23 (A few more NPcomplete problems) Read: Sec. 7.5. (Read ahead: Secs. 8.18.3)
 07/19: Lecture 24 (PSPACE) Read: Secs. 8.18.3. (Read ahead: Secs. 8.48.6)
 07/22: Lecture 25 (PSPACEcompleteness)
 07/24: Lecture 26 (NL=coNL)
 07/26: Lecture 27 (Randomized Complexity, SchwartzZippel's Lemma)
 07/31: Lecture 28 (Interactive Proofs) Read: Sec. 10.1 and 10.4. (Read ahead: Sec. 9.1)
 08/2: Lecture 29 (Time and Space Hierarchy Theorems; Course Review) Read: Sec. 9.1.
Slides for lecture 1 (pdf) and (one note)
Finite Automaton and Turing Machine simulators

FiniteAutomaton simulator. You can draw a diagram for your finite automaton (using the instructions provided), and then see it run on an input of your choice. (Another FA simulator is here. It requires downloading and installing some Java software.)

Singletape Turing machine simulator (in Java). It can be programmed (using the simple syntax explained on the page), and then you can watch the TM simulate your program on an input of your choice. After entering your program and the initial tape contents into the appropriate windows, click the "Reset" button to load the program and the input. Then you can click "Run" to watch the machine run, or click "Step" to see its action step by step.