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.

4 Responses to “A Prediction: P == NP and within 5 years”

  1. mike Says:

    They are both variables. N would always have to be one.

  2. Dave Says:

    Hi,

    quite provocative post you have there ;)

    The problem of whether P == NP is definitely mathematically decidable: either the program “return true” or the program “return false” is a solution – we just don’t know which one.

    Good luck with waiting for P == NP!
    Dave

  3. Max Nanasy Says:

    @mike Not if P is zero.

  4. Charles Ros Says:

    Yeah, my head still hurts when I first came across this. Never dreamed with such a complex problem could actually exist. Kinda like…oh I don’t know, man seems to have an answer for everything, I’m sure someone will propose a solution to the P/NP paradox. Have fun…

Leave a Reply