Hacker News Reader

Comment by klodolph | Hacker News Reader

This is incorrect. You would need to find a polynomial algorithm for at least one "NP-hard" problem, not any problem in NP. And a polynomial, exact algorithm would not necessarily be superior to heuristics for relevant real-world NP problems such as 3SAT... what if the polynomial were O(N^1000)?

View on HN

NP-complete, actually. NP-hard problems don't have NP-complete equivalents.

NP-Complete are NP-Hard, inside NP.

Some NP-hard problems are NP-complete, but not all. I guess I should have said strictly NP-hard, thanks.

You are right, I confused NP with NP-hard. However, I think it's safe to assume that if a polynomial solution exists for a NP-hard problem, the complexity wouldn't be so incredibly high than it's better to use heuristics.

> I think it's safe to assume that if a polynomial solution exists for a NP-hard problem, the complexity wouldn't be so incredibly high than it's better to use heuristics.

How is this possibly safe to assume? The “heuristic” methods aim for a “good enough” solution rather than “the best solution”. Whyever would a polynomial time algorithm for exactly solving an NP-hard problem be faster than polynomial time “heuristic” algorithms (which depending on the acceptable solution quality can be relatively computationally simple)?

I felt exactly the same way. I personally think (which is worth next to nothing of course) that if it's ever proven that P=NP (unlikely), the results will be mostly impractical.

Reply on news.ycombinator.com