3 ms·
I believe what they are saying is that the entire field just assumes P != NP and so if the proof came to be P != NP, then most people would just have their inkl
by hervature 9y ago
I believe what they are saying is that the entire field just assumes P != NP and so if the proof came to be P != NP, then most people would just have their inklings confirmed and that's about it. It wouldn't really cause a shift in research in any of the CS departments. However, if P = NP, you can bet on a renewed interest in finding polynomial time algorithms.
- dom0 9y agoThere are a bunch of major assumptions which are not rigorously proven, but generally assumed (hence assumption) to be correct, frequently backed up by a large body of heuristic evidence. P!=NP is one of them.
- x3n0ph3n3 9y agoThat's like saying no one is interested in a solution to the Riemann Zeta Hypothesis. It's thought to be true, and mathematics have been derived from its assumed truth, but there is still major interest in proving it to be true.
- hervature 9y agoThe difference is that if Riemann Zeta is incorrect, many theorems that are based on the hypothesis being correct will also be invalidated. Whereas assuming P != NP is limited to a relatively small area of complexity theory. I think a much more equivalent conjecture in complexity theory would be the unique games conjecture. Because the unique games conjecture already provides certain problems to be completely characterized (see: https://en.wikipedia.org/wiki/Unique_games_conjecture#Relevance https://en.wikipedia.org/wiki/Unique_games_conjecture#Releva...). Thus, proving this to be true kind of closes the chapter on many problems. Whereas proving P != NP true still leaves many gaps open.
- hnaccy 9y agoA proof would likely involve novel techniques and open up new areas of research.
- deleted 9y ago[deleted]