NP Completeness

Very related to ReadingRoom/TuringMachines

Book Resources

• Book	P, NP, and NP-Complete	Notes
  Sipser	7.2-7.4	Has good explanation of Cook's Thm in secn ?, 3-CNF-SAT in secn ?
  Hopcroft, Motwani, Ullman	10.1-10.2
  Lewis and Papadimitriou
  Cormen	34

Online Resources

To start:

• Wikipedia: NP-complete - The basics. Formal definition, some example problems, references to more complexity classes.

• An Introduction to Computational Complexity - Highly readable. Starts by explaining big-Oh, then moves on to P and NP.

  • Part C of the above goes into more depth in P and NP, including some basic proof techniques.

• Clay: P vs NP - a very short, very sweet summary. (Incidently, this is the site for the P vs NP Millenium Problem, a $1M prize problem run by Clay)

Going a bit further:

• http://www.nada.kth.se/~viggo/problemlist/compendium.html A bunch of NP optimization problems

• Google directory: Complexity Theory - Lots of links we haven't had time to triage yet.

• The Complexity Zoo - lots of complexity classes

  • Complexity Zoo: NP

  • Complexity Zoo: P

• Cook's Thm(pdf) - proof notes. May be a bit over our heads.