# Simplest proof of NP-completeness

The only first-principles "proof" that a problem is NP-complete I encountered is from Introduction to algorithms, and deals with the circuit-satisfiability problem. According to the authors, many details in the proof are omitted.

What is the simplest first-principles proof that a problem is NP-complete that thoroughly presents all the technical details?

• I assume you want a proof that is not a reduction to a different NP-complete problem, but rather a direct proof from the definition of NP-completeness? Wikipedia has a nice writeup of such a proof: en.wikipedia.org/wiki/Cook%27s_theorem. Feb 28, 2012 at 14:19
• @AlextenBrink: I assume you mean (polynomial-time) reduction from a different NP-complete problem (in addition to an NP membership proof)? Just nit-picking, but the difference is, of course, crucial. Mar 5, 2012 at 12:16
• @Magnus Lie Hetland: you are of course completely right. Unfortunately, comments can't be edited, so I can't correct it. Mar 5, 2012 at 14:18

What about { (M,$1^t$) : M is a turing machine that, run on a blank tape, accepts within t steps} ?