After sending his paper to several leading researchers in the field and acquiring support, Vinay Deolalikar from HP Labs has recently published P ≠ NP to the web. While it has yet to be externally verified by folks such as the Clay Mathematics Institute, it looks very promising. Indeed, this very well represent a Millennium Prize for Mr. Deolalikar. For those interested in additional information, check out Greg Baker’s blog (which broke the story). Very exciting!
To read more about the history and importance of P vs. NP, please consult these sources:
- P versus NP Problem (Wikipedia)
- Stephen Cook, The P versus NP Problem
- Madhu Sudan, The P versus NP Problem
- Lance Fortnow, The Status of the P versus NP Problem
- Stephen Cook, The Importance of the P versus NP Question