DMdmitrygusev·Jan 20, 2011
With what error?
Can you please file an issue here: https://github.com/anjlab/sat3/issues
and provide link to CNF file?
In The polynomial algorithm for 3-SAT problem (or P=NP)anjlab
sat3
Java2011–2011
anjlab / sat3
sat3
Reference Implementation of Romanov's Polynomial Algorithm for Boolean 3-SAT Problem
4Distinct people
4Mentions
0Explicit recommenders
93GitHub stars
What to know before exploring
What it is
Reference Implementation of Romanov's Polynomial Algorithm for Boolean 3-SAT Problem
GitHub
Where it is used
No documented product use has been verified yet.
What people are saying
No recommendation phrase was found in the indexed comments.
No classified warning is attached to this page. Read the discussions before treating silence as approval.
Also in these discussions
No other repository is repeatedly linked in the same discussions.
This week on Hacker News
Nov 7–Nov 14 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/14/2026, 3:56:07 PM UTC.
No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.
Mentions over time
HN mentions by hour4 dated mentions
Observed mentions: 2011-01-19 23:50:57 UTC to 2011-01-20 12:03:18 UTC.
Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.
View mention counts and date ranges
| Period | Start (UTC) | End (exclusive, UTC) | Mentions | Submissions | Comments |
|---|---|---|---|---|---|
| Jan 19, 23:00 | 2011-01-19 23:00:00 UTC | 2011-01-20 00:00:00 UTC | 2 | 0 | 2 |
| Jan 20, 00:00 | 2011-01-20 00:00:00 UTC | 2011-01-20 01:00:00 UTC | 1 | 0 | 1 |
| Jan 20, 01:00 | 2011-01-20 01:00:00 UTC | 2011-01-20 02:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 02:00 | 2011-01-20 02:00:00 UTC | 2011-01-20 03:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 03:00 | 2011-01-20 03:00:00 UTC | 2011-01-20 04:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 04:00 | 2011-01-20 04:00:00 UTC | 2011-01-20 05:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 05:00 | 2011-01-20 05:00:00 UTC | 2011-01-20 06:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 06:00 | 2011-01-20 06:00:00 UTC | 2011-01-20 07:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 07:00 | 2011-01-20 07:00:00 UTC | 2011-01-20 08:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 08:00 | 2011-01-20 08:00:00 UTC | 2011-01-20 09:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 09:00 | 2011-01-20 09:00:00 UTC | 2011-01-20 10:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 10:00 | 2011-01-20 10:00:00 UTC | 2011-01-20 11:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 11:00 | 2011-01-20 11:00:00 UTC | 2011-01-20 12:00:00 UTC | 0 | 0 | 0 |
| Jan 20, 12:00 | 2011-01-20 12:00:00 UTC | 2011-01-20 13:00:00 UTC | 1 | 0 | 1 |
What Hacker News says
4 sourcesIt looks like the paper is fairly straightforward. It purports to give a polynomial time algorithm for 3-SAT.
Interesting facts:
- It is a O(n^4m) algorithm, where n is the number of boolean variables and m is the number of disjunctions.
- It not only tells you whether the formula is satisfiable or not, but gives you the satisfying values.
- The author claims to have implemented and tested the algorithm on reasonably sized problems, though I don't see his code posted anywhere (?). Someone else appears to have implemented it here: https://github.com/anjlab/sat3.
- The author references no prior work, just review papers on the problem itself.
In The polynomial algorithm for 3-SAT problem (or P=NP)If this were the situation I would agree with you, however an independent programmer has implemented his algorithm and posted it on github with instructions (https://github.com/anjlab/sat3) on how to run it on k-SAT instances. Because of this, I believe it increases the claim's reputability; it is easier to confirm or reject his algorithm and claim.
In The polynomial algorithm for 3-SAT problem (or P=NP)I know nothing about N=NP debate, but does the claim P=NP and the existence of a published algorithm (https://github.com/anjlab/sat3) make this claim easier to verify than the claim P!=NP. Isn't the point that P=NP has great practical significance that will be immediately recognized?
In The polynomial algorithm for 3-SAT problem (or P=NP)