Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



I 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)


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.


On the first P algorithm found, or any P algorithm?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: