Communications of the ACM
ACM News
Issues In the Proof That P?np
The mathematics community is working on deciding whether or not to accept Vinay Deolalikar's claimed proof that P≠NP. Two computer science professors, Richard Lipton of Georgia Tech and Kenneth Regan of the University of Buffalo, are tracking the discussion. They thank Deolalikar, a Principal Research Scientist at HP Research Labs in Palo Alto, CA, for tackling the problem but state that many serious issues have been raised about his proof. They summarize the problems, each of which has been raised by more than one mathematician:
- The ordered-structure issue.
- The paper may not handle tupling correctly.
- The LFP characterization of P may not accomplish what the author needs.
- The paper may target the wrong hardness phase of randomized k-SAT.
From Gödel's Lost Letter and P=NP
View Full Article
No entries found