3 ms·
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
by Fargren 16y ago
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.
- klodolph 16y agoThis 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)?
- StavrosK 16y agoNP-complete, actually. NP-hard problems don't have NP-complete equivalents.
- Fargren 16y agoYou 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.
- jacobolus 16y ago> 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)?
- wlievens 16y agoI 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.