*What's Up With That P=NP Question Anyway?*

It dives into a fundamental question of computer science which just states that it is sometimes very hard to find a solution to a problem, but very easy to verify it.

A good analogy is doing groceries. Say, you did your groceries and you want to fit them into the back of your trunk. Will it fit?

Now, it is

*hard*to find whether a solution exists to the above problem. You might need to try all possible ways of packing them into your trunk, before you find out that they do, or maybe don't, fit. But is

*easy*to verify any given solution, just pack your stuff according to a description and see if it fits, and you're done.

*What's Up With That Phase Transition Anyway?*

Phase transition is also an easy concept. When given the above problem 'fitting groceries in my trunk,' it basically deals with for what list of groceries you might find a solution fast.

In case you bought two match-boxes, and try to fit them, you can easily determine a solution. The problem is

*underconstrained*. In case you also bought two refrigerators, you can easily see there isn't a solution, just making one fit may already be hard. The problem is

*overconstrained*. But for a lot of lists of groceries, which might fit seemingly, or might just not, you're on a

*phase transition bound*where, suddenly, there are no computer programs which can determine in a fast manner whether they'll fit or not. The best computer programs may even take the rest of the life of this universe spending time determining that.

*Does That Matter?*

The problem is that we don't know whether better programs can exist. And that's the heart of the problem. Oversimplifying the fitting problem again: If P!=NP, which it does pragmatically at the moment, no algorithms exists, and if P=NP, somewhere an algorithm may exist.

*What Did Deolalikar Probably Do?*

I didn't read his proposal. But he starts of with a construction, assumes P=NP, and shows that that, according to what we know now, cannot compute fast solutions since we'll hit phase transitions. But that's the crux: Phase transitions only exist since we don't have fast algorithms, therefor most of us assume P!=NP. He just proved his own assumption.

Pragmatically, he may be right. But, pragmatically, for a lot of applications, 22/7 just equals π.