Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
3  
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). –  D.W. Apr 26 at 21:58
    
This has been answered in our reference question, but I think this question has merit for the specific "beginner-confusion" it addresses. –  Raphael Apr 27 at 11:37
add comment

1 Answer 1

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.

share|improve this answer
    
Just imagine we had to do it without reductions from SAT. I doubt there'd be more than a handful of problems proven to be NP-hard. –  G. Bach Apr 27 at 13:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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