‘The films I made are as autobiographical as fiction can be.’ –Jean Eustache
It is the greatest question in computer science. A negative answer would likely give a fundamentally deeper understanding of the nature of computation. And a positive answer would transform our world: Computers would acquire mind-boggling powers such as near-perfect translation, speech recognition and object identification; the hardest questions in mathematics would melt like butter under computation’s power; and current computer security methods would be as easy to crack as a TSA-approved suitcase lock.
So when Vinay Deolalikar, a computer scientist at Hewlett Packard labs in India, sent an email on August 7 to a few top researchers claiming that P doesn’t equal NP — thereby answering this question in the negative and staking a claim on the million-dollar Millennium Prize offered by the Clay Mathematics Institute — it sent shock waves through the community. Usually, computer scientists groan when they find such a claim in their Inbox, expecting the typical amateurish “proof” with the same hoary errors. But Deolalikar is a recognized and published scientist, and his paper had novel ideas from promising areas of research.
