Thinking in polynomial time

“The Status of the P versus NP Problem” is the title of an excellent paper in September’s Communications of the ACM. For many developers, it may be a look at the world you live in, where solving complicated problems in a reasonable amount of time may be easy – or it may be difficult. For others, it’s a rare peek into the world of algorithmic computer science.

My own state is somewhere in the middle. I clearly remember studying the classes of problems deemed NP – non-polynomial time as I think of it, but more properly defined as nondeterministic polynomial time. However, that was a long time ago.

P problems – those solvable in polynomial time – are generally easy to code. NP problems aren’t. They seek to do tasks like determining if a large integer is prime, or finding the absolute best way to pack load a delivery truck with odd-sized packages, or working out the gravitational paths of multiple objects. Generally speaking, NP problems can be only solved in exponential time; however, the solution often can be verified in polynomial time. (It might take years to factor a 512-bit number, but you can verify in a couple of nanoseconds that the factors are correct simply by multiplying them together.)

The CACM paper, by Lance Fortnow (pictured), a professor at Northwestern University’s McCormick School of Engineering, discusses the ancient question: Is there a way of transforming NP problems so that they can be solved in polynomial time? In other words, does P = NP? (If I remember my computer science correctly, there is a hypothesis that says that if any NP problem can be transformed into a P problem, then all NP problems can be so transformed.)

Should we find out that P = NP, then a whole range of problems will become easier. Long-range weather forecasting is an NP problem. Wouldn’t it be nice to solve? On the other hand, public-key encryption only works because the factoring of very large integers is an NP problem. If P = NP, then the underpinnings of today’s best crypto algorithms will be washed away.

In a nutshell, it still seems that P ≠ NP. However, there is no proof one way or another. As Prof. Fortnow says, the question is still open. There’s a lot more to the subject – I recommend reading the paper. You’ll enjoy it; at least, I did.