5 ms·
We have lived with NP \neq P being the prevailing opinion for nearly three decades. If NP \neq P there will be no dramatic engineering aspects coming from the
by brg 16y ago
We have lived with NP \neq P being the prevailing opinion for nearly three decades. If NP \neq P there will be no dramatic engineering aspects coming from the result, as focus has long ago shifted towards heuristics and approximations. If NP \eq P, we may still not know any underlying algorithm for solving TSP efficiently, but there will be hope of finding one and the search will continue.
But it may be more realistic to consider what happens if NP \neq P. The main change for CS will be the shift in the focus of research.
If the proof is correct, there will be a brief flurry in which people find simplifications, restatements, and shallow applications to other areas of research.
But for three decades this has been the motivating problem in theoretical computer science. I think there will be a lot of soul searching, and perhaps a subdued atmosphere in the research community, but then attention will turn back to the topics in which people are actively exploring. However, there will perhaps never again be such a unifying, fundamental problem in CS.
- Fargren 16y agoIf 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.