P != NP

Pravi, da pri dokazu uporablja ene fizikalne postulate. To ni dobro, to ne bo šlo skoz. Ne more.

Komentar od nekoga iz http://news.ycombinator.com/item?id=158...

Several points on the question of whether the proof is likely to be correct:

*As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.)

*Therefore a proper assessment is going to take a while. Until then we can only speculate :-)

*While the crank attempts at P =? NP are statistically much more common (http://news.ycombinator.com/item?id=347..., this isn't one of them. The author is a legit computer scientist: http://www.hpl.hp.com/personal/Vinay_De...

*On the other hand he hasn't published much on complexity theory and isn't known in that community. Which is weird but not necessarily a red flag.

*Looking at his papers, it's possible he's been working on this for about 5+ years -- he has two threads of research, basic and industrial, and the former line of publications dried up around 2004.

*On the other hand I don't think anyone knew he was working on this. The only known serious effort was by Ketan Mulmuley at U Chicago.

*It has been known that the straightforward combinatorial approaches to P =? NP aren't going to work, and therefore something out of left field was required (http://web.cs.wpi.edu/~gsarkozy/3133/p7.... Mulmuley's plan of attack involved algebraic geometry.

*This paper uses statistical physics. This approach doesn't seem to have been talked about much in the community; I found only one blog comment http://rjlipton.wordpress.com/2009/04/2...... which mentions the survey propagation algorithm. (Deolalikar's paper also talks about it tangentially.)

*If the statistical physics method used here is powerful enough to resolve P != NP, then there's a good chance it is powerful enough to have led to many smaller results before the author was able to nail the big one. It's a little weird we haven't heard anything about that earlier.

*Finally, since the author is using physics-based methods, there's the possibility that he is using something that's a "theorem" in physics even though it is technically only a conjecture and hasn't actually been proven. Physicists are notorious for brushing technicalities under the rug. It would be very unlikely that the author didn't realize that, but still worth mentioning.

*If that is indeed what happened here, but the rest of the proof holds up, then we would be left with a reduction from P != NP to a physics conjecture, which could be very interesting but not ground breaking.
Conclusion: overall, it certainly looks superficially legit. But in non peer reviewed solutions of open problems there's always a high chance that there's a bug, which might or might not be fixable. Even Andrew Wiles's first attempt at FLT had one. So I wouldn't get too excited yet.

Zanimivo je najbrž tudi to, da je odločanje, kako boš zavrtel in kam položil Tetris lik, tudi NP problem.

Ko smo že omenili MineSweeperja -- Tetris je NP kompleksen.

Ni znano, če je kakšen polinomski algoritem za igranje.

Critticallov output je vedno samo domneva, takoimenovana "conjecture", ne kakšen matematični dokaz.

Lahko bi dal naprimer za nek algoritem, ki ga poznamo in je eksponenten, polinomsko rešitev, ki je pa le domneva. Brez dokaza, samo z nekaj milijardami true positive in nobenega negative.

Logičnega dokazovanja matematičnih teoremov ne obvlada.