# 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 problemsGoogle directory: Complexity Theory - Lots of links we haven't had time to triage yet.

The Complexity Zoo - lots of complexity classes

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