6
$\begingroup$

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?

$\endgroup$

closed as off topic by Kaveh Mar 29 '11 at 1:20

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Can you explain why the downvote? $\endgroup$ – Adrian Petrescu 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$ – Adrian Petrescu 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