Deolalikar P vs NP paper: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
m Deolaikar's P!=NP paper moved to Deolalikar's P!=NP paper: spelling error in name. |
|||
| Line 9: | Line 9: | ||
== Possible issues == | == Possible issues == | ||
=== Issues with LFP === | |||
=== Issues with d1RSP === | |||
=== Barriers === | === Barriers === | ||
Any P vs NP proof must deal with the three known barriers described below. The concerns around this paper have not yet reached this stage yet. | |||
==== Relativization ==== | ==== Relativization ==== | ||
| Line 17: | Line 24: | ||
==== Algebraization ==== | ==== Algebraization ==== | ||
== Terminology == | == Terminology == | ||
Revision as of 23:43, 9 August 2010
Note: This is currently an UNOFFICIAL page on Deolalikar's P!=NP paper, and is not currently affiliated with a Polymath project.
The paper
- Vinay Deolalikar's web page
- First draft (date?)
- Second draft (date?)
Possible issues
Issues with LFP
Issues with d1RSP
Barriers
Any P vs NP proof must deal with the three known barriers described below. The concerns around this paper have not yet reached this stage yet.
Relativization
Natural proofs
Algebraization
Terminology
Online reactions
- P ≠ NP Greg Baker, Greg and Kat’s blog, August 7 2010
- A proof that P is not equal to NP? Richard Lipton, Godel's lost letter and P=NP, August 8 2010
- Issues In The Proof That P≠NP Richard Lipton and Ken Regan, Godel's lost letter and P=NP, August 9 2010
