Big news on P vs NP?

August 19, 2010

Perhaps you’ve heard of the Millenium Problems, the seven $1,000,000 prize math problems. They’re pretty hard. In fact, I kind of assumed we’d see one solved every forty or fifty years. Well, an eccentric Russian named Grigori Perelman solved one already (the Poincare Conjecture). And now someone (his name is Deolalikar) has taken a serious shot at the P vs NP problem. We’ll see if he is vindicated and claims the prize.

P vs NP is the most important problem in theoretical computer science right now. Wikipedia’s explanation of it is so good, I’m going to quote at length:

Informally, it asks whether every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer.

More thoroughly [note: I’m not hooking up the links for the quoted parts. Just search for them on wikipedia if you want to know more]:

In essence, the question P = NP? asks:

Suppose that solutions to a problem can be verified quickly. Then, can the solutions themselves also be computed quickly?

The theoretical notion of quick used here is that of an algorithm that runs in polynomial time. The general class of questions for which some algorithm can provide an answer in polynomial time is called “class P” or just “P”.

For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it may be possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is called NP.

Consider the subset sum problem, an example of a problem which is easy to verify but whose answer is suspected to be theoretically difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer “yes, because {−2, −3, −10, 15} add up to zero” can be quickly verified with three additions. However, finding such a subset in the first place could take more time; hence this problem is in NP (quickly checkable) but not necessarily in P (quickly solvable).

An answer to the P = NP question would determine whether problems like the subset-sum problem that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P does not equal NP, it would mean that some NP problems are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

Roughly, polynomial time means that as the complexity of the problem grows, the difficulty in solving it doesn’t grow too fast.

The weird thing is, most experts (though not all!) agree that P≠NP. So why is the proof important?

To answer, I refer you to the beautiful discussion here, from which I cherry-pick the following quote from the mathematician Atiyah:

I think it is said that Gauss had ten different proofs for the law of quadratic reciprocity. Any good theorem should have several proofs, the more the better. For two reasons: usually, different proofs have different strengths and weaknesses, and they generalise in different directions—they are not just repetitions of each other.

The lesson for teachers and students of the subject? Your study doesn’t end with a right answer…
it shifts into high gear.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments