Sunday, August 8, 2010

P != NP

Dr. Vinay Deolalikar of HP Labs has written a paper proving that P != NP. This has been at the center of theoretical computer science for almost as long as computers have been envisioned. This is good news for cryptography but bad news for optimization of some useful problems, like traveling sales man.

The paper has not been peer reviewed, so the jury is still out on whether he is correct.