3 ms·
From this it seems that the question itself might have been hopelessly naive Is there any evidence that P might be equal to NP? This seems different from other
by raverbashing 7y ago
From this it seems that the question itself might have been hopelessly naive
Is there any evidence that P might be equal to NP? This seems different from other famous conjectures like Fermat's Last Theorem or Riemann's Theorem where what's hard is finding a counterexample that disproves the theory.
- someguy12342 7y agoI think RJ Lipton (blog author) and Knuth believe it could be true. However, most complexity theorists don't (I think Fortnow does a survey of theorists on this every few years). Knuth says something like "well all it would take is a single algorithm for any of these hundreds of problems". A fine take for the godfather of algorithms. At the same time, there are many people who have in some sense tried to find such an algorithm, even non-explicitly (e.g. factoring would be in P if P = NP). Moreover, there is a lot of complexity theoretic work which makes it hard to believe it to be true (I think Scott Aaronson's blog has some presentable information about this)
- lonelappde 7y agohttp://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions http://www.informit.com/articles/article.aspx?p=2213858&WT.m... Note that Knuth does not believe that the constant factor on the P algorithm be will be less than the size of the entire Universe.
- saagarjha 7y agoOn the first P algorithm found, or any P algorithm?