<p>A couple of months ago there was a minor hubbub about a paper published on ArXiV by V. F. Romanov titled <a href="http://arxiv.org/abs/1011.3944" rel="nofollow"><em>Non-Orthodox Combinatorial Models Based on Discordant Structures</em></a> which claimed to give a polynomial-time algorithm for 3-SAT, thus proving that $P=NP$. He even went as far as posting a <a href="https://github.com/anjlab/sat3" rel="nofollow">reference implementation</a> of the algorithm publicly.</p>

<p>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 <em>wasn't</em> successful, obviously, so does anybody know what the problem with this paper ended up being?</p>

CC BY-SA 2.5
2011-03-29T00:15:56.803Z
Can you explain why the downvote?
Adrian Petrescu
CC BY-SA 2.5
2011-03-29T00:40:24.857Z
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.
Adrian Petrescu
CC BY-SA 2.5
2011-03-29T00:49:04.510Z
The question seems to be [in scope according to the FAQ](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics/281#281), but you would probably get a better answer if the question was focused on some particular technical claim.
arnab
CC BY-SA 2.5
2011-03-29T01:04:33.257Z
@arnab: Thanks for that; I hadn't seen those guidelines since they're on the Meta site and not the FAQ (yet). I'll try to edit my question soon with some concrete technical points from the article.
Adrian Petrescu
CC BY-SA 2.5
2011-03-29T01:23:57.923Z
Please see [this FAQ item](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics/281#281). General questions about correctness of an unpublished not-peer-reviewed pre-print claiming to solve an open problem is off-topic for this site.
Kaveh
CC BY-SA 2.5
2011-03-29T01:26:26.303Z
Okay, having read the policy, I understand the reason for closing, but I humbly submit that a question on a neighboring website from 7 months ago is not really an "FAQ item" that you should expect new users to have read before posting.
Adrian Petrescu
CC BY-SA 2.5
2011-03-29T01:30:33.393Z
@Adrian, there is a link to it in [the official FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) (last item). We are here to remind the new users about the policies of this site. :)
Kaveh
CC BY-SA 2.5
2011-03-30T03:26:56.813Z
@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.
Aryabhata
<cc.complexity-theory><p-vs-np>
What is the status of Vladimir Romanov's proof that P=NP?
Adrian Petrescu
# What is the status of Vladimir Romanov's proof that P=NP?

(Asked by: username_0 on 2011-03-28)

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*](http://arxiv.org/abs/1011.3944) 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](https://github.com/anjlab/sat3) 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?

**Tags:** cc.complexity-theory, p-vs-np
> **Comments:**
> **username_0**: Can you explain why the downvote?  
> **username_0**: 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.  
> **username_1**: The question seems to be [in scope according to the FAQ](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics/281#281), but you would probably get a better answer if the question was focused on some particular technical claim.  
> **username_0**: @arnab: Thanks for that; I hadn't seen those guidelines since they're on the Meta site and not the FAQ (yet). I'll try to edit my question soon with some concrete technical points from the article.  
> **username_2**: Please see [this FAQ item](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics/281#281). General questions about correctness of an unpublished not-peer-reviewed pre-print claiming to solve an open problem is off-topic for this site.  
> **username_0**: Okay, having read the policy, I understand the reason for closing, but I humbly submit that a question on a neighboring website from 7 months ago is not really an "FAQ item" that you should expect new users to have read before posting.  
> **username_2**: @Adrian, there is a link to it in [the official FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) (last item). We are here to remind the new users about the policies of this site. :)  
> **username_3**: @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.  

---

## 0 answers

