Friday, January 14, 2011

P vs. NP page

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)


Simon said...

Where would you put your money if you had to?

Anonymous said...

Fantastic Y! :)

Yaroslav Bulatov said...

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)

Anonymous said...

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.

Yaroslav Bulatov said...

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.

marinir seo said...
This comment has been removed by a blog administrator.
remo said...

<a href=">Digital Marketing Internship Program in Bangalore</a>

draj said...

Excellent machine learning blog,thanks for sharing...
Seo Internship in Bangalore
Smo Internship in Bangalore
Digital Marketing Internship Program in Bangalore

Kanye Co Jamila said...

Great Article
IEEE final year projects on machine learning

JavaScript Training in Chennai

Final Year Project Centers in Chennai

JavaScript Training in Chennai

john said...

فرزاد فرزین
علی یاسینی
شهاب مظفری
احسان خواجه امیری

upmusic said...

ِDownload New persian Songs
دانلود آهنگ دیس لاو
دانلود آهنگ ماشین
دانلود آهنگ جدید

John said...

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

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