A Prediction: P == NP and within 5 years

So after reading this poll of mathematicians and computer scientists who have given the problem 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.

This entry was posted on Thursday, September 29th, 2011 at 6:36 am and is filed under Math. You can follow any responses to this entry through the Atom feed. Both comments and pings are currently closed.