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?
What about { (M,$1^t$) : M is a turing machine that, run on a blank tape, accepts within t steps} ?

The proof of NP-completeness is a simple exercise from the definition.