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

<p>The proof of NP-completeness is a simple exercise from the definition.</p>

CC BY-SA 3.0
2012-02-28T15:26:32.987Z
2012-02-28T15:26:32.987Z
Manu
<p>The only first-principles "proof" that a problem is NP-complete I encountered is from <a href="http://en.wikipedia.org/wiki/Introduction_to_Algorithms" rel="nofollow">Introduction to algorithms</a>, and deals with the circuit-satisfiability problem. According to the authors, many details in the proof are omitted.</p>

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

CC BY-SA 3.0
2012-03-05T12:16:43.670Z
@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
CC BY-SA 3.0
2012-03-05T14:18:19.853Z
@Magnus Lie Hetland: you are of course completely right. Unfortunately, comments can't be edited, so I can't correct it.
Alex ten Brink
CC BY-SA 3.0
2012-02-28T14:19:48.480Z
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: http://en.wikipedia.org/wiki/Cook%27s_theorem.
Alex ten Brink
<cc.complexity-theory><np-hardness>
Simplest proof of NP-completeness
Randomblue
# Simplest proof of NP-completeness

(Asked by: username_0 on 2012-02-28)

The only first-principles "proof" that a problem is NP-complete I encountered is from [Introduction to algorithms](http://en.wikipedia.org/wiki/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?

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_2**: 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: http://en.wikipedia.org/wiki/Cook%27s_theorem.  
> **username_1**: @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.  
> **username_2**: @username_1: you are of course completely right. Unfortunately, comments can't be edited, so I can't correct it.  

---

## 1 answers

### Answer by username_3 on 2012-02-28. Score: 17 | Accepted answer

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.


---

