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.

5 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…

  5. world cup qualifier results 2014 Says:

    Coral’s best worth guess within the World Cup countdown has arrived!
    Gets odds of forty four/1 on any participant from Ligue 1, still contracted to a French top-flight staff
    when the tournament has ended, being the highest scorer in Brazil

    With play actually opening up – as many matches have in the second
    round of group matches following cagey encounters within the first – Montolivo as soon as extra showcased
    his long-vary talents but again Paston proved equal to his shot by
    palming it away from hazard as the pressure mounted.
    New Zealand coach Ricki Herbert soon replaced Fallon with
    Wooden, who went so close to clinching a profitable purpose as he turned Cannavaro inside-out earlier
    than guiding a nicely FIFA world cup brazil packages-struck low shot just the incorrect aspect of
    the post. Based on the tune of the day, Hearn didn’t
    really care who received that 12 months, as he had the rest of them signed up.
    This wasn’t completely true, clearly. The usual contenders were arriving in Sheffield, some in a significantly better place psychologically than others.

Leave a Reply