A couple of months ago there was a minor hubbub about a paper published on ArXiV by V. F. Romanov titled Non-Orthodox Combinatorial Models Based on Discordant Structures which claimed to give a polynomial-time algorithm for 3-SAT, thus proving that $P=NP$. He even went as far as posting a reference implementation of the algorithm publicly.

However, as is usually the case with these things, the public attention didn't last long enough for me to hear of any resolution to this claim. I assume this means it wasn't successful, obviously, so does anybody know what the problem with this paper ended up being?

  • 3
    $\begingroup$ Can you explain why the downvote? $\endgroup$ Mar 29 '11 at 0:15
  • 2
    $\begingroup$ I should perhaps emphasize that, at the time, it was considered a serious attempt (despite the unusual result), and not one of the many crackpot claims out there. $\endgroup$ Mar 29 '11 at 0:40
  • 7
    $\begingroup$ The question seems to be in scope according to the FAQ, but you would probably get a better answer if the question was focused on some particular technical claim. $\endgroup$
    – arnab
    Mar 29 '11 at 0:49
  • 6
    $\begingroup$ @Adrian, there is a link to it in the official FAQ (last item). We are here to remind the new users about the policies of this site. :) $\endgroup$
    – Kaveh
    Mar 29 '11 at 1:30
  • 5
    $\begingroup$ @Adrian: meta.cstheory is not just a "neighbouring" website. It is the site where the policy of cstheory is decided. This is a feature of all stackexchanges sites. Every site has a corresponding meta, and browsing the questions tagged faq will serve you well on the main site. $\endgroup$
    – Aryabhata
    Mar 30 '11 at 3:26