Hacker News Reader

Comment by Fargren | Hacker News Reader

If P were to be equal to NP and we found a polynomial algorhythm to just one NP problem, then through polynomial conversion, we should be able to solve all, or at least most, NP problems in polynomial time. This would be very superior to heuristics even for the most naive of implementations for most relevant NP problems.

View on HN

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)?

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