Communications of the ACM
ACM News
Deolalikar Responds To Issues About His P?np Proof
Mathematician Vinay Deolalikar
Credit: NDTV
Vinay Deolalikar is standing by his P≠NP claim and proof. He has updated his paper several times in an effort to answer some questions that have been raised about it. However, the following questions about the proof's correctness have been posed by UCLA Professor Terence Tao:
- Does Deolalikar's proof, after only minor changes, give a proof that P ≠NP?
- Does Deolalikar's proof, after major changes, give a proof that P≠NP?
- Does the general proof strategy of Deolalikar (exploiting independence properties in random k-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?
From Gödel's Lost Letter and P=NP
View Full Article
No entries found