Topic | |
Lecture #1 (01/11) |
Syllabus Introduction Representation Computational task, search problems, decision problems |
Lecture #2 (01/13) |
Uniform models, algorithms, Turing machines |
Lecture #3 (01/18) |
Uncomputable functions, the Halting problem |
Lecture #4 (01/20) |
Universal machines, Kolmogorov complexity |
Lecture #5 (01/25) |
Reduction of the Halting Problem to the Modified Post Correspondence Problem |
Lecture #6 (01/27) |
Example of the resulting tiles for a simple Turing machine Reduction of MPCP to PCP |
Lecture #7 (02/01) |
The Cobham-Edmonds thesis/Strong Church-Turing thesis Universal machines Space complexity Oracle machines and Turing reductions |
Lecture #8 (02/03) |
Search version: finding vs checking, PF, PC Decision version: proving vs verifying, P, NP, proof system |
Lecture #9 (02/08) |
Equivalence of the search and decision versions of NP |
Lecture #10 (02/10) |
Traditional definition of NP in terms of non-deterministic Turing machines Equivalence of the definitions based on non-deterministic Turing machines and verification procedures |
Lecture #11 (02/15) |
Solutions for problems on HW1 |
Lecture #12 (02/17) |
Definition of oracle TM Turing reduction Cook reduction Karp reduction Levin reduction |
Lecture #13 (02/22) |
Reducing optimization problems to search problems |
Lecture #14 (02/24) |
Implicit decision problems Self-reducibility |
Lecture #15 (03/01) |
Overview to NP-completeness Definitions of NP-complete/hard |
Lecture #16 (03/03) |
Class canceled |
Lecture #17 (03/15) |
Topics for presentations |
Lecture #18 (03/17) |
Guidelines for Ex. 4.18 |
Lecture #19 (03/22) |
Discussion of solutions for HW 2 |
Lecture #20 (03/24) |
Proof of existence of NP-complete problems |
Lecture #21 (03/29) |
Proof of NP-completeness of CSAT and SAT |