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

## Wednesday, August 30, 2017

## Monday, August 28, 2017

## Friday, August 25, 2017

### Day 3

Reducibility and NP-Completeness

Papers:

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.

## Wednesday, August 23, 2017

### 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.

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.

## Monday, August 21, 2017

### 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.

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

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

Subscribe to:
Posts (Atom)