4 ms·
I forget my CS in old age. Am I correct in saying, roughly speaking, that everybody knows that P!=NP but we just can’t prove it? Sort of like Fermat’s Last Th
by gorgoiler 5y ago
I forget my CS in old age. Am I correct in saying, roughly speaking, that everybody knows that P!=NP but we just can’t prove it?
Sort of like Fermat’s Last Theorem: the proof is out there.
- sova 5y agoA mathematician can write an equality without anybody raising an eyebrow, but as soon as someone suggests that we can choose the optimal answer on the first "guess" everyone wants to rekindle the Spanish Inquisition. If we can go from "guess" to "obvious solution" then it stands to reason that P=NP. Of course, this is a debate that likely has no clear path without some stroke of insight, because the axiomatic "truth" that confirms it one way or the other is not reachable by induction alone. There is likely an island of consistent axiomatic logical statements that we must not only wait for someone to reach by happenstance, but to decipher and know what to do with them. According to Fermat, his proof was omitted due to lack of space in the margin. I suppose it's good to let others share in the glory now and again, if on centuries-delay.
- mdoms 5y agoWhat?
- bawolff 5y agoSo what you're saying is: If there exists an algorithm that always guesses correctly then we can solve NP problems? That's just the definition of NP restated. One of the definitions of NP is all the problems that can be solved in polynomial time if at every choice we had a method of always guessing correctly. The question of NP=P is if such a method can actually be implemented in polynomial time on a Turing machine. So yes, you are correct, it stands to reason that if NP=P, then NP=P.
- hnfong 5y agoI don't know whether the GP intends this, but one fun way of understanding the GP's comment is: If you believe really so strongly that P!=NP without actual proof, you're actually just making a guess, and then saying you can make good guesses. But the process of doing so implies you actually believe P=NP.
- bawolff 5y agoSo according to this poll http://www.cs.umd.edu/~gasarch/papers/poll.pdf http://www.cs.umd.edu/~gasarch/papers/poll.pdf only about two thirds think P!=NP (unless you also count the independent group as also believing we cant prove it). So seems like the majority opinion but not universal.
- gs17 5y agoHis later polls seem to have trended towards higher percents: https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.p...
- ak_111 5y agoThere are a few notable exceptions who believe that P=NP, Knuth being the most notable in my opinion. He gives a justification (though it is a bit technical) for this that I also find convincing.
- rpmuller 5y agoI asked Scott Aaronson what he thought about Knuth's ideas, and he said something along the lines of when you're as famous as Knuth, you can get away with saying nonsense like that.
- d--b 5y agoWhat everyone agrees on though is that NP problems are slow to solve by today's known algorithms.