6

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?

Saurav Maheshkar
  • 261
  • 1
  • 8
user1532146
  • 115

2 Answers2

17

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.

Noah Schweber
  • 245,398
  • 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? – user1532146 Oct 03 '16 at 20:15
  • 5
    @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! – Noah Schweber Oct 03 '16 at 20:17
  • 3
    @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. – Noah Schweber Oct 03 '16 at 20:22
  • (See here for more details on polytime reductions.) – Noah Schweber Oct 03 '16 at 20:24
  • 10
    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. – Hayden Oct 03 '16 at 21:08
  • Great! SAT make it clear. – user1532146 Oct 04 '16 at 00:34
  • 1
    @Hayden Since when is it pedantry to just point to the definition? – adelval Oct 04 '16 at 10:11
1

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.

user2715500
  • 19
  • 4
    This mostly just restates the claim. Maybe give the definition of what NP-complete is, that will make things much more clear. – Caleb Stanford Oct 03 '16 at 20:41