Princeton
University
|
COS 487/MAT 407
|
|
Course Summary
What is computation? What can be computed in principle with unbounded computational resources? What can be computed efficiently? What can we gain by formally modeling computation and how do different models relate to one another? How can models highlight different resources of computations, such time, memory, communication, and randomness. We will consider these questions and others using a rigorous mathematical approach. We will discuss what we know as well as some of the central open problems in pure and applied mathematics, and specifically the P vs. NP problem.Prerequisites: COS 340/341 or equivalent math background (basically, the ability to do mathematical proofs).
About This Course
Text: Introduction to the Theory of Computation (3rd Edition) by Michael Sipser.Grading: The grade will be based upon assignments, which will be handed out every roughly two weeks. A week will be given to complete each assignment. Collaborating with your classmates on assignments is encouraged, with the exception of the last assignment that should be completed alone. The last assignment will constitute for 30% of the grade and the rest of the assignments for 70%.
Assignments should be typed. LaTeX is strongly recommended, it's free and can be downloaded here.
Here is a suggested LaTaX template for problem sets' solutions (.tex), this is what it looks like once compiled (.pdf).
Administrative Information
Lectures: Tue-Thu 1:30-2:50pm, Room: Friend Center 016, Signup on Piazza: Link
Professor: Gillat Kol
- 316 CS Building gkol@princeton.edu
TA: Raghuvansh Saxena rrsaxena@princeton.edu
Honor Code for This Course
The grade is based on problem sets. You are encouraged to work in groups up-to three people on each problem set, accept the last problem set (groups may change between problem sets). However, we ask that you dedicate enough time to think about each problem by yourself before consulting others. You must write up each problem solution by yourself without assistance and are asked to identify your collaborators on problem sets. You must complete the last problem set by yourself and are not allowed to discuss it with anyone until after the deadline.You may consult your course notes, the text (Sipser), and any resource given in this webpage. The assignment questions may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.
Schedule and Readings
| Date |
Lecture topics |
Reading |
| Lecture 1, Sep 14 |
Introduction to Course Topics - Computational models. - Computability theory and connections to mathematical logic. - Complexity theory and the P vs. NP problem. - Deterministic finite automata (DFA): definition, examples. |
Chapter 1.1 of text. |
| Lecture 2, Sep 19 |
Topic: Finite Automata (cont'd) - Nondeterministic finite automata (NFA): definition, equivalence of DFAs and NFAs. - Regular expressions: definition, examples. |
Chapters 1.2-1.3 of text. |
| Lecture 3, Sep 21 |
Topic: Finite Automata (cont'd) - Regular expressions: equivalence to DFAs. - Nonregular languages: the pumping lemma. |
Chapters 1.3-1.4 of text. |
| Lecture 4, Sep 26 |
Topic: Streaming Algorithms - Definition. - The distinguishably technique for space lower bounds. - The most frequent element problem - space upper and lower bounds. |
Notes on streaming algorithms by Ryan Williams and Luca Trevisan's. Notes on finding the majority element of a stream. |
| Lecture 5, Sep 28 |
Topic: Streaming Algorithms (cont'd) - The number of distinct elements problem - space upper and lower bounds. - The randomized streaming model: randomized algorithm for sampling and number of distinct elements. |
Notes on streaming algorithms by Ryan Williams and Luca Trevisan. |
Lecture 6, Oct 3 |
Topic: Turing Machines - Deterministic Turing machines: definition, examples. - Multi-tape Turing machine: definition, equivalence to single-tape Turing machines. |
Chapters 3.1,3.2 of text. |
Lecture 7, Oct 5 |
Topic: Turing Machines (cont'd) - Nondeterministic Turing machines: definition, equivalence to deterministic Turing machines. - The Church-Turing Thesis. - Definition of decidable and recognizable languages. |
Chapters 3.2,3.3,4.1 of text. |
Lecture 8, Oct 10 |
Topic: Computability Theory (cont'd) - Examples of decidable and recognizable languages. - Diagonalization arguments and undecidable languages (Acceptability and Halting). - Unrecognizable languages. |
Chapter 4 of text. |
Lecture 9, Oct 12 |
Topic: Computability Theory (cont'd) - Reductions: definition, examples. |
Chapters 5.1,5.3 of text. |
Lecture 10, Oct 17 |
Topic: Computability Theory (cont'd) - More reductions. - Rice's theorem. |
Chapter 5.1 of text. Proof of Rice's theorem is the answer to Problem 5.28. |
Lecture 11, Oct 19 |
Topic: Computability Theory (cont'd) - Connections to mathematical logic: * Proof systems. * Gödel's first incompleteness theorem. |
Notes on unprovable statements by Luca Trevisan. |
Lecture 12, Oct 24 |
Topic: Computability Theory (cont'd) - Connections to mathematical logic: * Gödel's second incompleteness theorem. * The Church-Turning theorem (checking whether a statement has a proof is undecidable). - Kolmogorov complexity: definition. |
Notes on unprovable statements by Luca Trevisan. Chapter 6.4 of text. |
Lecture 13, Oct 26 |
Topic: Computability Theory (cont'd) - Kolmogorov complexity: undecidability of the compression problem. - The Extended Church-Turing Thesis. - Polynomial time algorithms and the P complexity class. - The time hierarchy theorem. |
Notes on Kolmogorov complexity by Luca Trevisan. Chapters 7.1-7.2,9.1 of text. |
Lecture 14, Nov 7 |
Topic: Complexity Theory (cont'd) - The NP complexity class: definition via verifiers, examples. - The P vs. NP problem. - Gaining from P ≠ NP: cryptography and derandomization. |
Chapter 7.3 of text. |
Lecture 15, Nov 9 |
Topic: Complexity Theory (cont'd) - Definition of NP via non-deterministic Turing machines. - Polynomial time reductions: definition and examples. |
Chapters 7.3-7.4 of text. |
Lecture 16, Nov 14 |
Topic: Complexity Theory (cont'd) - NP-complete problems: definition. - Cook-Levin Theorem: 3SAT is NP-complete. |
Chapter 7.4 of text. |
Lecture 17, Nov 16 |
Topic: Complexity Theory (cont'd) - Cook-Levin Theorem: 3SAT is NP-complete (cont'd). - NP-complete problems: examples. |
Chapters 7.4-7.5 of text. |
Lecture 18, Nov 21 |
Topic: Complexity Theory (cont'd) - Ladner's Theorem: infinitely many levels of difficulty in NP (statement only). - The PSPACE complexity class: definition. - TQBF is PSPACE-complete. |
Chapters 8.2-8.3 of text. |
Lecture 19, Nov 28 |
Topic: Complexity Theory (cont'd) - PSPACE and winning strategies in two-players games. - The coNP complexity class. - PSPACE = NPSPACE = coNPSPACE. |
Chapter 8.3 of text. |
Lecture 20, Nov 30 |
Topic: Complexity Theory (cont'd) - Oracle machines, relativizing proofs. - Baker-Gill-Solovay Theorem: diagonalization does not suffice to settle the P vs. NP problem. |
Chapter 9.2 of text. |
Lecture 21, Dec 5 |
Topic: Complexity Theory (cont'd) - Randomized algorithms and the BPP complexity class: definition, examples. - The P vs BPP problem. |
Chapter 10.2 of text. |
Lecture 22, Dec 7 |
Topic: Complexity Theory (cont'd) - Interactive proofs: the graph-nonisomorphism example, IP = PSPACE (statement only). - Zero knowledge: the graph-isomorphism example. |
Chapter 10.4 of text. Arora-Barak book Chapter 8.3. |
Lecture 23, Dec 12 |
Topic: Complexity Theory (cont'd) - The PCP theorem (Probabilistically Checkable Proofs). - One-time pads. - One-way functions. |
Chapter 10.6 of text. Arora-Barak book Chapters 18.1 and 10.1. |
| Lecture 24, Dec 14 |
Topic: Cryptography (cont'd) - Public key encryptions and the Diffie-Hellman Key exchange protocol. - Cryptographic pseudo-random generators and the Goldreich-Levin Theorem. |
Arora-Barak book Chapters 10.2-10.3. |