The P/NP Problem

I was reading about cryptography recently, even before I came across this.

I'll get back to the NYT story. First, some related materials.

I was reading, for reasons I won't go into now, about "challenge-response authentication," (CRA), geek-speak for the password protection of particular websites.

It is called CRA because a server "challenges" a computer's user to produce a password and the user responds. Anyway, the client-server exchange is a simple bit of cryptography, arranged so that the password doesn't have to be sent out into the world, where a hacker might leap upon it, naked.

CRA is generally regarded as a second-best solution to the problem of computer security by those who think it would be really cool to encrypt everything. But, alas, that is expensive and impractical.

This leads back to the NYT story to which I linked you above, and a mathematical puzzle. Define "P" as the set of all problems that can be easily solved. Define "NP" as the set of all problems that are difficult to solve, but that can be easily recognized as accurately solved once somebody else has done so. Think of a crossword puzzle. You may be much better at doing crosswords than I am. But I can lok over your completed puzzle, and the clues, and after the fact I can recognize that you got it right.

It seems intuitively obvious that P and NP are not the same set. After all, in that case, for me the crossword puzzle falls within NP but outside of P.

All crytography depends upon that notion that P does not equal NP. There must be problems (like finding out my password) which are difficult for hackers to solve, but easy for another machine to recognize as having been solved. If P does equal NP, it means everything is in principle hackable. If the two sides of the communication can recognize each other, then third parties can figure out the password, because one of those requires NP, the other requires P, and we've just supposed they are the same.

Thus, it was important that someone prove in a rigorous scientific fashion that they aren't the same. We can all breath easier, according to Vinay Deolalikar, a mathematician and electrical engineer at Hewlett-Packard.

But maybe not. As the NYT story (and this blog entry) both indicate, Deolalikar may not have the last word.

Great! Another "dismal joust"! I won't pretend that I can follow that blog entry at all. Can anybody who understands these things lket me know if I've even been making sense in the above exposition of what the problem is?