Re:Predicting When P=NP Is Resolved
by someguy12342 on Sunday December 22, 2019 @05:47PM
(#21860159)
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)
[ Parent
| on HN ]
Re:Predicting When P=NP Is Resolved
by lonelappde on Sunday December 22, 2019 @09:36PM
(#21861109)
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.