3 ms·

I've heard that if a polynomial-time solution was found for an NP-hard problem, that would mean that all NP-hard problems can be solved in polynomial time. Is t

I've heard that if a polynomial-time solution was found for an NP-hard problem, that would mean that all NP-hard problems can be solved in polynomial time. Is this true, and why is that?

random_coder 13y ago
It's not true. If a poly-time solution is found for NP-hard problem, then it's not necessarily true that other NP-hard problems can be solved in polynomial time. However, if poly-time solution for an NP-hard implies every NP-complete (and thus every problem in NP) has a polynomial time solution.
mjfl 13y ago
Edit: This might not be true for NP-hard, but I misread your post and assumed you meant NP-complete. Yes. It is because every problem in NP can be "reduced" (transformed into) an NP-complete problem in polynomial time. Therefore if a polynomial time solution for an NP-complete problem exists, the algorithm: Have problem: 1) Transform problem into NP-complete problem (polynomial time) 2) Solve NP-complete problem (polynomial time) Two polynomial time steps make a polynomial time algorithm. The proof that every problem in NP is polynomial-time reducible to an NP-complete problem is pretty long and complicated, involving the formalism of Turing Machines, but it can be found in most textbooks on the theory of computation and I believe it is called the Cook-Levin Theorem (that proves the 3SAT is NP-complete, and then most other theorems show that 3SAT is reducible to them).
- leibniz 13y ago
  but not every NP-hard problem is in NP
  - mjfl 13y ago
    this is true, see edit
deleted 13y ago
[deleted]
gphilip 13y ago
No, this is not true. But the following is true: if a polynomial-time solution was found for an NP-hard problem, that would mean that all problems in the class NP can be solved in polynomial time [1]. This would include all those NP-hard problems which also happen to be in the class NP. NP-hard can be read as "as hard to solve as any problem in the class NP". So if we can solve one of these hard problems in polynomial time, then -- by the meaning of NP-hard -- we can solve all problems in the class NP in polynomial time. The reason why your statement is not true as it is, is that there are NP-hard problems which are not inside the class NP. These problems are "much harder than" any problem in the class NP and so, being able to solve all problems in NP in polynomial time does not mean that these "harder than all of NP" problems can also be solved in polynomial time. Check the Wikipedia entry on NP-hard for an example of such a "harder-than NP, but also NP-hard" problem. https://en.wikipedia.org/wiki/NP-hard https://en.wikipedia.org/wiki/NP-hard A problem which is both (i) NP-hard, and (ii) in NP is said to be NP-complete. If a polynomial-time solution was found for an NP-hard problem, that would mean that all NP-complete problems can be solved in polynomial time (because they are all in NP). [1] There is a fine point here turning on what "can be solved" means. If we take "can be solved" to mean "there exists an algorithm", then this statement is fine. Otherwise ... but that is an arcane point anyway.
- jmcgough 13y ago
  Thanks for the explanation - I didn't understood the difference between NP-hard and NP-complete when I asked this (the wiki article on NP-hard helped to clarify!).

I've heard that if a polynomial-time solution was found for an NP-hard problem, that would mean that all NP-hard problems can be solved in polynomial time. Is this true, and why is that?

random_coder 13y ago

It's not true. If a poly-time solution is found for NP-hard problem, then it's not necessarily true that other NP-hard problems can be solved in polynomial time. However, if poly-time solution for an NP-hard implies every NP-complete (and thus every problem in NP) has a polynomial time solution.

mjfl 13y ago

Edit: This might not be true for NP-hard, but I misread your post and assumed you meant NP-complete. Yes. It is because every problem in NP can be "reduced" (transformed into) an NP-complete problem in polynomial time. Therefore if a polynomial time solution for an NP-complete problem exists, the algorithm: Have problem: 1) Transform problem into NP-complete problem (polynomial time) 2) Solve NP-complete problem (polynomial time) Two polynomial time steps make a polynomial time algorithm. The proof that every problem in NP is polynomial-time reducible to an NP-complete problem is pretty long and complicated, involving the formalism of Turing Machines, but it can be found in most textbooks on the theory of computation and I believe it is called the Cook-Levin Theorem (that proves the 3SAT is NP-complete, and then most other theorems show that 3SAT is reducible to them).

leibniz 13y ago
but not every NP-hard problem is in NP
- mjfl 13y ago
  this is true, see edit

deleted 13y ago

[deleted]

gphilip 13y ago

No, this is not true. But the following is true: if a polynomial-time solution was found for an NP-hard problem, that would mean that all problems in the class NP can be solved in polynomial time [1]. This would include all those NP-hard problems which also happen to be in the class NP. NP-hard can be read as "as hard to solve as any problem in the class NP". So if we can solve one of these hard problems in polynomial time, then -- by the meaning of NP-hard -- we can solve all problems in the class NP in polynomial time. The reason why your statement is not true as it is, is that there are NP-hard problems which are not inside the class NP. These problems are "much harder than" any problem in the class NP and so, being able to solve all problems in NP in polynomial time does not mean that these "harder than all of NP" problems can also be solved in polynomial time. Check the Wikipedia entry on NP-hard for an example of such a "harder-than NP, but also NP-hard" problem. https://en.wikipedia.org/wiki/NP-hard https://en.wikipedia.org/wiki/NP-hard A problem which is both (i) NP-hard, and (ii) in NP is said to be NP-complete. If a polynomial-time solution was found for an NP-hard problem, that would mean that all NP-complete problems can be solved in polynomial time (because they are all in NP). [1] There is a fine point here turning on what "can be solved" means. If we take "can be solved" to mean "there exists an algorithm", then this statement is fine. Otherwise ... but that is an arcane point anyway.

jmcgough 13y ago
Thanks for the explanation - I didn't understood the difference between NP-hard and NP-complete when I asked this (the wiki article on NP-hard helped to clarify!).