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.
John said...

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

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

Anonymous said...

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