, 1 min read
How to get everyone talking about your research!
Deolalikar claims to have solved the famous P versus NP problem. Is the proof correct? Some influential researchers doubt it: Scott Aaronson is betting 200k$ of his own money against Deolalikar.
What I find most interesting is that Deolalikar did not submit the paper to a journal, as far as I know. He didn’t even post it on arxiv like Perelman. Yet, he is receiving much attention. His name is being tweeted several times a minute. Many of the most influential theoretical computer scientists are reacting to the paper. He is getting the best peer review possible. Most similar papers don’t get so much attention.
Why is this paper different?
- Everyone seems to agree that the paper is well written, it has nice (color!) figures and the reference section appears up-to-date and complete. If your result is important, communicate it well.
- Deolalikar has published just a handful of papers in theoretical computer science, and none at the major conferences. But he has enough peer-reviewed research papers to be treated as a peer.
- While I doubt he was hired to work on complexity theory, Deolalikar is an industry researcher at HP. Being paid to do research might make you more credible.
Further reading: Deolalikar’s publication list on DBLP, A Proof That P Is Not Equal To NP? by Lipton and P ≠NP by Baker.
Update: Porreca has the best write-up on reactions to this paper.
Update 2: The consensus after two weeks is that the proof wrong and unfixable.