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?

onionesquereality said...

Fantastic Y! :)

Yaroslav 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)

mkatkov 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 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.

pak gendoet said...