# 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. – Alex ten Brink Feb 28 '12 at 14:19
@AlextenBrink: Thanks. – Randomblue Feb 28 '12 at 14:24
@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. – Magnus Lie Hetland Mar 5 '12 at 12:16
@Magnus Lie Hetland: you are of course completely right. Unfortunately, comments can't be edited, so I can't correct it. – Alex ten Brink Mar 5 '12 at 14:18

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