Here's a page linking 65
attempts of resolving P vs NP problem. A couple of papers were published in peer-reviewed journals or conferences, while most are "arxiv" published. Some statistics:
- 35 prove P=NP
- 28 prove P!=NP
- 2 prove it can go either way (undecidable)
8 comments:
Where would you put your money if you had to?
Fantastic Y! :)
Simon: either != or undecidable because otherwise some physicist would've found an algorithm by now. I'm saying physicists because the tend to discover things 50 years before they are proven mathematically (ie, percolation threshold, Kasteleyns holographic counting algorithm)
I'm physicist by the first degree ;).
I like you idea to put open source implementation, although I do not see its direct application. In the current form, it will be probably quite slow, compared with existing heuristic methods for 3SAT problem, because the dimensionality of the resulting SDP problem grows fast- n^2 monomials, and n^4 SDP variables. Since the polynomial guaranteed method for SDP is second order one need to store Hessian for n^4 variables, that leads to n^8 variables. Practically, on modern computer, one cannot solve the problem with more than, say, hundred vertices in the original max-cut problem. Therefore, the problem becomes not (very limited) interesting from engineering and machine learning point of view. I came to PvsNP question from machine learning problem related to human perception of textures.
It is possible that there is a shortcut, due to homotopy continuation, but that I do not know for sure.
Thanks for suggestion, anyway.
Models with 100 vertices are actually common for testing binary inference algorithms. Binary MAP reduces to max-cut, and an exact algorithm that's fast enough to run on 100 vertex model is an interesting open problem.
THANKS FOR THE INFORMATION...
دانلود آهنگ های پرطرفدار جدید
دانلود آهنگ شاد
Fantastic Article. I am sharing a TikTok Video
have a look at it and if you want to Download TikTok Without Watermark
you can visit this website
Post a Comment