4 ms·
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
by someguy12342 7y ago
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)
- 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?