P not equal to NP | Hacker News Reader

P not equal to NP

arxiv.org

13 pointslainon9 comments

Just going by the first section, I can anticipate a problem here. The last paragraph of the first section suggests that the problem of finding a Hamilton cycle is not in P because some cycles are maximal solutions without being a maximum solution. However, the same could be said of the problem of finding a maximum matching -- a maximal matching need not be a maximum matching -- and yet that problem is in P.

I haven't yet checked the formal conditions to see whether they'll apply to the matching problems, but I bet they will. (The fact that the paper contains no instances of the word "matching", meaning it never explains why this condition doesn't apply to the matching problem even though it looks like it should, is not encouraging.) If so this proof cannot be correct.

https://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Here's a link to a list of P vs NP proofs that didn't work out. "Making it to arxiv" and "sounding reasonable" are usually pretty good filters but for some reason this problem has attracted a lot of trouble.

Note that this hasn't been updated in a while. For instance Norbert Blum's attempt from 2017 (now acknowledged as mistaken) is missing.

wow the biggest takeaway is that mathematicians need to have a mechanism to proof that their proofs are right! Over 120 'proofs' which have proven to be wrong, are other fields in mathematics equally error ridden? Koq seems less like a toy but more like a necessity. Or those papers need to be called "attempt for a proof, sketch of the proof, proposition of a proof" before there is community consensus. (which seems to be the unofficial reading anyway so this ticket can be closed)

The main step seems to be Lemma 2. The fact that the reductions are logspace is never actually used in the argument - so if this proof worked, it would also apply to arbitrary reductions, and the same argument would show that NP is not contained in, say, EXP.

The fact that there are no inequalities anywhere throughout the paper is the real tip-off that this is not a serious attempt.

Kinda insanely difficult summary there :)

Yawn.

WOW!! Another one after Vinay Deolalikar's! I lack the mathematical expertise but would certainly love to hear what experts have to say on this one.

Claims of P != NP are pretty common; I wouldn't get so excited just yet...

Reply on news.ycombinator.com