P and NP

Recently, Vinay Deolalikar self-published a proof that P is not equal to NP. So what does that mean exactly?

P is short for Polynomial, and NP is short for Non-deterministic Polynomial. To understand the exact difference requires you to understand Turing machines (usually a senior level CS class). P is the class of problems that can be solved in polynomial time on a deterministic Turing machine in polynomial time, and NP is the class that can be solved on a non-deterministic Turing machine in polynomial time. Here’s the catch: so far, no non-deterministic Turing machines exist. There’s speculation that quantum computers are non-deterministic Turing machines, but not a proof that I know of.

Another way of thinking about P and NP problems is how long it takes for a computer to solve the problems – is it “easy” (P) or “hard” (NP). Most classic computer science problems are NP – the traveling salesman, factoring integers… The computer can verify the answer in P time, so the current approach is to make a best guess, verify it, then make another guess.

What does this mean for most people? Most people have never heard of P or NP – heck, a lot of computer/IT people probably haven’t unless they’ve studied theoretical computer science – and even most of us who’ve heard of it would rather forget it. But it really does matter for security. One of the NP problems is factoring integers – what public key cryptography is based on. There is an assumption – based on years of practice, but no proofs – that NP is not equal to P. If NP were ever shown to be equivalent to P, then our current asymmetric cryptography solutions would be blown out of the water and we’d all have to find new algorithms to use. If NP were proved to be not equal to P, we’ve got some more time 🙂

So far, the reviews I’ve heard of Deolalikar’s paper is that it’s a great start, but it has a few flaws, so we still don’t know if P is or is not equal to NP.