<p>First of all, Cook actually showed that the problem of whether a logical expression is a tautology is $\mathbb{NP}$-complete under Cook <a href="http://en.wikipedia.org/wiki/Polynomial-time_reduction#Types_of_reduction">reductions</a>. The proof however works by replacing them with Karp reductions to show that $SAT$ is $\mathbb{NP}$-complete, in the modern sense of the term.</p>

<p>As for whether Cook understood the significance of a $\mathbb{NP}$-complete problem not being in $\mathbb{P}$, going through the actual <a href="https://www.cs.toronto.edu/~sacook/homepage/1971.pdf">paper</a>  shows that he did. However, I believe it wasn't until Karp's <a href="http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems">list of 21 complete problems</a> that the practical significance of Cook's result began to be understood. </p>

CC BY-SA 3.0
2015-06-08T14:35:12.027Z
2015-06-08T14:35:12.027Z
chazisop
<p>If I understand correctly, to prove that problem $A$ is NP hard, you need to pick all possible problems $B_{i}$ that are in NP and then prove that they reduce to $A$ by using a polynomial time computable function, that maps instances of each $B_{i}$ to instances of $A$.</p>

<p>Once you find the first NP hard problem, by using reductions you can then find that many other problems are either NP Complete or NP Hard. However I imagine that this depends. If you are unlucky, then maybe all $B_{i}$ problems reduce to $A$, but $A$ reduces nowhere else, so your proof is essentially useless.</p>

<p>My question is about the motivation that Stephen Cook behind showing that the SAT problem is NP hard. Did he see a lot of potential behind this problem? Did he know that if he showed that this problem is NP hard then a lot of other problems could be shown to be NP hard as well?</p>

<p>In short, what is the story behind this proof? Because after studying some basic complexity theory, it really seems like this proof was one of the most significant ones in this area. </p>

CC BY-SA 3.0
2015-06-08T14:32:26.467Z
If $A$ is $\mathbb{NP}$-complete, then by definition it is in $\mathbb{NP}$ in addition to being $\mathbb{NP}$-hard. So for every other $\mathbb{NP}$-complete problem $C$ there must be a reduction $A \leq C$. I suggest you separate this fact on the first two paragraphs from the rest of the questions, since it is trivial. I'll answer the second part separately.
chazisop
CC BY-SA 3.0
2015-06-08T16:35:47.600Z
First, I don't think this is on-topic for this site, this seems more suitable for [cs.se]. You don't seem to have even read the paper.
Kaveh
CC BY-SA 3.0
2015-06-08T16:52:28.923Z
Even if there was no other problem it would still be very significant that there is a problem in NP which is universal for NP. And in the paper Steve proves that a few other problems are NP-complete. AFAIU, the significance of the results was clear for the people at the conference.
Kaveh
CC BY-SA 3.0
2015-06-08T18:49:50.320Z
the question is somewhat backward. _nobody_ could have foreseen the widespread significance of P/NP distinction in CS in early days (its full implications still "being felt"), apparently nothing like the phenomenon was imagined by anyone at the time (~1970). Cook was closer than anybody at the time. even with mere logic/ code/ math, a top visionary. but, it was still abstract in Cooks paper. one could draw a parallel to "undecidability" in Turings 1936 paper. undecidability was more theoretical and not imagined to be so significant & have such major applied implications either at the time.
vzn
CC BY-SA 3.0
2015-06-08T18:54:08.473Z
on other hand there is some case to be made that [Gödel](https://rjlipton.wordpress.com/the-gdel-letter/) did anticipate some of the P/NP distinction/ significance in a letter to von Neumann 1956
vzn
<soft-question><ho.history-overview><cook-levin>
Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?
jsguy
# Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?

(Asked by: username_0 on 2015-06-08)

If I understand correctly, to prove that problem $A$ is NP hard, you need to pick all possible problems $B\_{i}$ that are in NP and then prove that they reduce to $A$ by using a polynomial time computable function, that maps instances of each $B\_{i}$ to instances of $A$.

Once you find the first NP hard problem, by using reductions you can then find that many other problems are either NP Complete or NP Hard. However I imagine that this depends. If you are unlucky, then maybe all $B\_{i}$ problems reduce to $A$, but $A$ reduces nowhere else, so your proof is essentially useless.

My question is about the motivation that Stephen Cook behind showing that the SAT problem is NP hard. Did he see a lot of potential behind this problem? Did he know that if he showed that this problem is NP hard then a lot of other problems could be shown to be NP hard as well?

In short, what is the story behind this proof? Because after studying some basic complexity theory, it really seems like this proof was one of the most significant ones in this area.

**Tags:** soft-question, ho.history-overview, cook-levin
> **Comments:**
> **username_1**: If $A$ is $\mathbb{NP}$-complete, then by definition it is in $\mathbb{NP}$ in addition to being $\mathbb{NP}$-hard. So for every other $\mathbb{NP}$-complete problem $C$ there must be a reduction $A \leq C$. I suggest you separate this fact on the first two paragraphs from the rest of the questions, since it is trivial. I'll answer the second part separately.  
> **username_2**: First, I don't think this is on-topic for this site, this seems more suitable for [cs.se]. You don't seem to have even read the paper.  
> **username_2**: Even if there was no other problem it would still be very significant that there is a problem in NP which is universal for NP. And in the paper Steve proves that a few other problems are NP-complete. AFAIU, the significance of the results was clear for the people at the conference.  
> **username_3**: the question is somewhat backward. _nobody_ could have foreseen the widespread significance of P/NP distinction in CS in early days (its full implications still "being felt"), apparently nothing like the phenomenon was imagined by anyone at the time (~1970). Cook was closer than anybody at the time. even with mere logic/ code/ math, a top visionary. but, it was still abstract in Cooks paper. one could draw a parallel to "undecidability" in Turings 1936 paper. undecidability was more theoretical and not imagined to be so significant & have such major applied implications either at the time.  
> **username_3**: on other hand there is some case to be made that [Gödel](https://rjlipton.wordpress.com/the-gdel-letter/) did anticipate some of the P/NP distinction/ significance in a letter to von Neumann 1956  

---

## 1 answers

### Answer by username_1 on 2015-06-08. Score: 18 | Accepted answer

First of all, Cook actually showed that the problem of whether a logical expression is a tautology is $\mathbb{NP}$-complete under Cook [reductions](http://en.wikipedia.org/wiki/Polynomial-time_reduction#Types_of_reduction). The proof however works by replacing them with Karp reductions to show that $SAT$ is $\mathbb{NP}$-complete, in the modern sense of the term.

As for whether Cook understood the significance of a $\mathbb{NP}$-complete problem not being in $\mathbb{P}$, going through the actual [paper](https://www.cs.toronto.edu/~sacook/homepage/1971.pdf) shows that he did. However, I believe it wasn't until Karp's [list of 21 complete problems](http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems) that the practical significance of Cook's result began to be understood.


---

