9
$\begingroup$

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.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – chazisop Jun 8 '15 at 14:32
  • 7
    $\begingroup$ First, I don't think this is on-topic for this site, this seems more suitable for Computer Science. You don't seem to have even read the paper. $\endgroup$ – Kaveh Jun 8 '15 at 16:35
  • 4
    $\begingroup$ 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. $\endgroup$ – Kaveh Jun 8 '15 at 16:52
  • $\begingroup$ 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. $\endgroup$ – vzn Jun 8 '15 at 18:49
  • $\begingroup$ on other hand there is some case to be made that Gödel did anticipate some of the P/NP distinction/ significance in a letter to von Neumann 1956 $\endgroup$ – vzn Jun 8 '15 at 18:54
17
$\begingroup$

First of all, Cook actually showed that the problem of whether a logical expression is a tautology is $\mathbb{NP}$-complete under Cook reductions. 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 shows that he did. However, I believe it wasn't until Karp's list of 21 complete problems that the practical significance of Cook's result began to be understood.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.