7
$\begingroup$

A problem is NP-complete if:

  1. It is in NP.
  2. All problems in NP can reduce to it.

It's number 2 that I'm concerned with here. I would be highly surprised if we knew every problem in NP. Based on that assumption, how do we know for sure that any problem is NP-complete? For example, how do we know that there's not some problem we don't know of that will reduce to the Boolean Satisfiability problem, but not the Clique problem? Or would such a problem be NP-Intermediate and therefore need P != NP to exist?

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ Have your read a textbook chapter on NP-completeness? That will answer your question. Do read about the proof that SAT is NP-complete. This is well-covered in standard sources, so you need to do more research before asking here (and you need to described what research you've done in the question). $\endgroup$ – D.W.♦ Apr 26 '14 at 21:58
  • $\begingroup$ This has been answered in our reference question, but I think this question has merit for the specific "beginner-confusion" it addresses. $\endgroup$ – Raphael♦ Apr 27 '14 at 11:37
13
$\begingroup$

We do know all problems in NP. Each problem in NP is given by a non-deterministic Turing machine running in polynomial time. Steve Cook (and, independently, Leonid Levin) proved that SAT is NP-complete by encoding the statement "Machine $M$ accepts $x$ given non-deterministic choices $y$" as a logical formula for every non-deterministic Turing machine; for a machine running in time $T$ and space $S$, the encoding has length roughly $O(TS)$, so when $M$ is polynomial time, the encoding has polynomial length. The corresponding SAT formula states that "for some $y$, machine $M$ accepts $x$ given non-deterministic choices $y$". This formula is satisfiable iff $M$ accepts $x$.

Having proven that one problem is NP-complete, there is no need to do this encoding again. To prove that some other problem $L$ is NP-hard, it is enough to reduce SAT to $L$. Every problem in NP is reducible to SAT, and via the auxiliary reduction, to $L$. This is the way NP-hardness results are proved nowadays, by reducing from some NP-hard problem.

| cite | 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.