6
$\begingroup$

Each NP problem is different, if one (even the hardest one) NP problem could be solved in polynomial time, I guess some related NP problems that could reduced to this one could also be solved in polynomial time. But why all? Does that mean all of other NP problems could be reduced to the one?

Some examples would be very helpful.

$\endgroup$
  • $\begingroup$ You are exactly right when you say "NP problems that could reduced to this one could also be solved in polynomial time". When "this" is an NP-complete problem, then any NP problem can be reduced to this problem. A problem in NP means it can be recognized by nondeterministic Turing machine in polynomial time, which means it can be reduced to SAT (Cook–Levin theorem), and SAT can be reduced to this problem (a problem is shown NP-complete by showing a reduction from SAT or some other NP-complete problem). E.g. Knapsack ≤ SAT ≤ TSP so solving TSP will solve Knapsack (in polynomial time). $\endgroup$ – ShreevatsaR Oct 3 '16 at 21:08
  • $\begingroup$ That's amazing! I need to go to learn SAT;-) $\endgroup$ – user1532146 Oct 4 '16 at 0:28
17
$\begingroup$

NP completeness means exactly that "all other NP problems could be reduced [in polynomial time] to the one", so yes, if a single NP-complete problem has a polynomial-time solution, then all NP problems do. See the formal definition.

Note that it is not obvious that NP-complete problems exist in the first place! E.g. maybe for every NP problem A, I can find an NP-problem B which is "polynomially harder" than A in the sense that there is no polytime-reduction from B to A. It turns out this isn't the case, but this takes proof. Some examples of NP-complete problems include:

  • Determining whether a propositional formula is satisfiable.

  • Determining whether a graph has a Hamiltonian path.

  • Determining whether a graph can be $k$-colored.

And there are many others; see this list.

$\endgroup$
  • $\begingroup$ But how is that possible? Like there are Travelling salesman problem and Knapsack problem, they are NP-complete problem, can we say if a polynomial time algorithm for TSP is found then Knapsack problem is also solved in polynomial time? $\endgroup$ – user1532146 Oct 3 '16 at 20:15
  • 4
    $\begingroup$ @user1532146 Yes, that's exactly it. If you're confused how this is possible, you might want to read the proof that e.g. SAT is NP-complete. It may seem odd, but it is completely true! $\endgroup$ – Noah Schweber Oct 3 '16 at 20:17
  • 3
    $\begingroup$ @user1532146 Specifically, "SAT is NP-complete" means "for any NP-problem A, there is a polytime algorithm $\alpha$ reducing A to SAT." Now if SAT is polytime-solvable - say, via an algorithm $\beta$ - this yields a polytime-solution to A: take an instance of A, turn it into an instance of SAT via $\alpha$, solve that instance via $\beta$, and use $\alpha$ to turn that solution into a solution to the original instance of A. Since this is (basically) the composition of three polytime functions, it is itself a polytime algorithm, and clearly solves A. $\endgroup$ – Noah Schweber Oct 3 '16 at 20:22
  • $\begingroup$ (See here for more details on polytime reductions.) $\endgroup$ – Noah Schweber Oct 3 '16 at 20:24
  • 9
    $\begingroup$ The pedant in me just wants to point out that NP-complete also means that the problem is in NP, otherwise it's just NP-hard. $\endgroup$ – Hayden Oct 3 '16 at 21:08
0
$\begingroup$

Because If one "NP-complete" problem can be solved without providing a general solution to the entire class of NP-complete problems, then the problem wasn't an NP-complete problem to begin with - by definition.

$\endgroup$
  • 4
    $\begingroup$ This mostly just restates the claim. Maybe give the definition of what NP-complete is, that will make things much more clear. $\endgroup$ – 6005 Oct 3 '16 at 20:41

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.