This post originated from an RSS feed registered with Java Buzz by Elliotte Rusty Harold. Original Post: A Prediction: P == NP and within 5 years Feed Title: The Cafes Feed URL: http://cafe.elharo.com/feed/atom/? Feed Description: Longer than a blog; shorter than a book Latest Java Buzz Posts Latest Java Buzz Posts by Elliotte Rusty Harold Latest Posts From The Cafes

So after reading this poll of mathematicians and computer scientists who have given the process way more thought than I have, I now suspect that indeed P == NP (though perhaps not usefully so). Why do I think this?

Quite simply, it seems to me that there are a lot of possible attacks on this problem, and that no one understands them all. The mathematicians claiming that P != NP (and especially that it won’t be solved soon) are basically claiming that the math they know won’t lead to a solution, whereas the mathematicians claiming that the problem will be solved are saying that they expect the math they know will lead to a solution. Knowing what won’t work is important, but for making predictions knowing what will is more important.

Of course, it could be that the problem will be solved and the solution will be that P != NP, as most folks seem to expect. Or it could be shown that the problem is undecidable (though that would likely take longer).

Perhaps I’m just an optimist, but I’m betting on a constructive solution to the problem. That is, I expect to see an algorithm soon that “solves” a known NP problem in polynomial time. That polynomial time may still be greater than the age of the universe, but it won’t be NP.