CMPT 308
Computability & Complexity - Summer 2019
Announcements
- Aug 2: I'll have 2-hour office hours on Wed, Aug 7, 11:30-13: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 19-27 (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 12-18 (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 7-12, excluding the Recursion Theorem. That is, Quiz 2 will cover TMs, decidability, undecidability, non-semi-decidability, 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 1-6 (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
- NP-completeness
- 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:30-14:20 | WMC 3260 |
| Wed | 13:30-14:20 | WMC 3260 |
| Fri | 13:30-14:20 | WMC 3260 |
- 4 in-class 50-min 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 grading-related 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 50-minute 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:30-18: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.1-3.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.1-3.3.)
- 05/24: Lecture 7 (Turing machines) Read: Sec. 3.2. (Read ahead: Sec. 4.2.)
- 05/27: Lecture 8 (Undecidability) Read: Sec. 4.1-4.2. (Read ahead: Secs. 5.1-5.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: Computability-based 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.1-7.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.1-7.3. (Read ahead: Sec. 7.4.)
- 07/3: Lecture 20 (NP-completeness) Read: Sec. 7.4. (Read ahead: Sec. 7..)
- 07/5: Lecture 21 (Cook-Levin's Theorem) Read: Sec. 7.4. (Read ahead: Sec. 7.5.)
- 07/15: Lecture 22 (NP-complete versions of SAT) Read: Sec. 7.4. (Read ahead: Sec. 7.5.)
- 07/17: Lecture 23 (A few more NP-complete problems) Read: Sec. 7.5. (Read ahead: Secs. 8.1-8.3)
- 07/19: Lecture 24 (PSPACE) Read: Secs. 8.1-8.3. (Read ahead: Secs. 8.4-8.6)
- 07/22: Lecture 25 (PSPACE-completeness)
- 07/24: Lecture 26 (NL=coNL)
- 07/26: Lecture 27 (Randomized Complexity, Schwartz-Zippel'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
-
Finite-Automaton 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.)
-
Single-tape 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.