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)

## 12 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...

<a href="http://www.chloros.in/digital-marketing-internship.htmlhttp://www.chloros.in/digital-marketing-internship.html>Digital Marketing Internship Program in Bangalore</a>

Excellent machine learning blog,thanks for sharing...

Seo Internship in Bangalore

Smo Internship in Bangalore

Digital Marketing Internship Program in Bangalore

Great Article

IEEE final year projects on machine learning

JavaScript Training in Chennai

Final Year Project Centers in Chennai

JavaScript Training in Chennai

فرزاد فرزین

علی یاسینی

شهاب مظفری

احسان خواجه امیری

ِDownload New persian Songs

دانلود آهنگ دیس لاو

دانلود آهنگ ماشین

دانلود آهنگ جدید

THANKS FOR THE INFORMATION...

دانلود آهنگ های پرطرفدار جدید

دانلود آهنگ شاد

Post a Comment