Day 5

Finished proof of Cook's theorem. Talked about potential NP-incomplete problems such as Graph Isomorphism, recently shown in quasipolynomial time by Laszlo Babai.

Day 4

Cook's proof that CNF-Satisfiability is NP-complete

Day 3

Reducibility and NP-Completeness

Papers:

• Steve Cook, The Complexity of Theorem-Proving Procedure
• Defined the P v NP problem and showed SAT is NP-complete
• Richard Karp, Reducibility Among Combinatorial Problems
• Shows 21 combinatorial problems NP-complete
• Michael Garey and David Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness
• The reference for NP-completeness. Every computer scientist should own this book.

Day 2

More introduction to computation, Turing Machines and time complexity. Defined P and briefly NP.

Papers mentioned:
Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem
Where he defines the Turing machine. Section 9 is worth reading where he basically defends his thesis that this model defines computability.
Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms
This paper started the field of computational complexity. It's major insight was to consider resources like time and memory as a function of the input size.
Jack Edmonds, Paths, Trees and Flowers
This paper gives a polynomial-time algorithm for graph matching and argues that polynomial-time is a reasonable stand in for efficient computation.
Alan Cobham, The Intrinsic Computational Difficulty of Functions
Cobham gave a similar argument for polynomial time.

Day 1

Guest lecture by Venkat.

Covered basics of Turing Machines, Complexity Classes and Polynomial Time.

Reminder that Assignment 0 is due Friday. Download and submit on T-Square.

Assignment 0

A short assignment is posted on T-Square and due on Friday.