<p>You can find all weird stuff out there...
For example, just google &quot;graph isomorphism problem 2022&quot;, and the first search result is this polytime algorithm... <a href="https://www.biorxiv.org/content/10.1101/2022.04.14.488296v1.full" rel="noreferrer">https://www.biorxiv.org/content/10.1101/2022.04.14.488296v1.full</a>
and result number six: <a href="https://www.researchgate.net/publication/360300519_Solving_graph_isomorphism_problem_in_polynomial_time_using_liner_algebra" rel="noreferrer">https://www.researchgate.net/publication/360300519_Solving_graph_isomorphism_problem_in_polynomial_time_using_liner_algebra</a>
Also, I've seen publications that are so confusing that it takes days to understand why they have a &quot;gap&quot;...</p>

CC BY-SA 4.0
2022-08-09T06:31:38.330Z
2022-08-09T06:37:06.967Z
2022-08-09T06:37:06.967Z
Avi Tal
<p>There's an algorithm (published on <a href="https://github.com/danvoicu1/nanosat/blob/main/PvsNP.pdf" rel="nofollow noreferrer">GitHub</a>) which is claimed to solve any 3-SAT formulation in polynomial time with a complexity of max O(n^6). I would usually brush claims like this away, but having looked at the code I found the approach worth a try, especially as the author provided a reference implementation and tested it exhaustively.</p>
<p>The author's reference implementation is in C#, so I ported it to C++ to run it on Linux and tested his algorithm on a lot of instances, from pure random generated instances over (hard) <a href="https://algo2.iti.kit.edu/balyo/papers/socs18slides.pdf" rel="nofollow noreferrer">Barthel</a> instances (Clause Distribution Control (CDC) based with r=4.3) up to hard industrial combinatoric instances - all of these have been correctly solved with less than n^6 steps. But why?</p>
<p>I'm scratching my head why the proposed algorithm performs that well. The main idea is comparable to a vertex cover problem search, but the best algorithms I have seen so far usually have exponential complexity, and cannot solve 3SAT in O(n^6). Based on the code there's indeed a maximum runtime of n^6 steps implemented.</p>
<p>I'm wondering if anyone here could provide a mathematical explanation (for the empirical demonstrated) performance (or if there are any pitfalls) and if it holds (generalised) for any 3-SAT problem.</p>
<p>Really appreciate your thoughts!</p>

CC BY-SA 4.0
2022-08-10T17:46:39.207Z
How big are these "hard" instances? I can fit an exponential curve to a curve of order 6 up to pretty large values.
cody
CC BY-SA 4.0
2022-10-17T16:13:30.753Z
@DanielM: if the author has a promising implementation of SAT, they can compete in SAT solver competitions, e.g., http://www.satcompetition.org/. That would provide good evidence that their algorithm is empirically efficient.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-08-02T04:37:10.193Z
please share your implementation or links since the original repository is now gone (and there is nothing in archive.org :/)
Nordine Lotfi
CC BY-SA 4.0
2023-01-06T13:57:45.730Z
Would you share your C++ port? This may be interesting to test.
Charles
<sat><polynomial-time><upper-bounds>
Solving 3-SAT in O(n^6)?
DanielM
# Solving 3-SAT in O(n^6)?

(Asked by: username_0 on 2022-08-08)

There's an algorithm (published on [GitHub](https://github.com/danvoicu1/nanosat/blob/main/PvsNP.pdf)) which is claimed to solve any 3-SAT formulation in polynomial time with a complexity of max O(n^6). I would usually brush claims like this away, but having looked at the code I found the approach worth a try, especially as the author provided a reference implementation and tested it exhaustively.

The author's reference implementation is in C#, so I ported it to C++ to run it on Linux and tested his algorithm on a lot of instances, from pure random generated instances over (hard) [Barthel](https://algo2.iti.kit.edu/balyo/papers/socs18slides.pdf) instances (Clause Distribution Control (CDC) based with r=4.3) up to hard industrial combinatoric instances - all of these have been correctly solved with less than n^6 steps. But why?

I'm scratching my head why the proposed algorithm performs that well. The main idea is comparable to a vertex cover problem search, but the best algorithms I have seen so far usually have exponential complexity, and cannot solve 3SAT in O(n^6). Based on the code there's indeed a maximum runtime of n^6 steps implemented.

I'm wondering if anyone here could provide a mathematical explanation (for the empirical demonstrated) performance (or if there are any pitfalls) and if it holds (generalised) for any 3-SAT problem.

Really appreciate your thoughts!

**Tags:** sat, polynomial-time, upper-bounds

> **Comments:**
> **username_1**: How big are these "hard" instances? I can fit an exponential curve to a curve of order 6 up to pretty large values.  
> **username_2**: @username_0: if the author has a promising implementation of SAT, they can compete in SAT solver competitions, e.g., http://www.satcompetition.org/. That would provide good evidence that their algorithm is empirically efficient.  
> **username_4**: Would you share your C++ port? This may be interesting to test.  
> **username_3**: please share your implementation or links since the original repository is now gone (and there is nothing in archive.org :/)  

---

## 1 answers

### Answer by username_5 on 2022-08-09. Score: 7

You can find all weird stuff out there...
For example, just google "graph isomorphism problem 2022", and the first search result is this polytime algorithm... <https://www.biorxiv.org/content/10.1101/2022.04.14.488296v1.full>
and result number six: <https://www.researchgate.net/publication/360300519_Solving_graph_isomorphism_problem_in_polynomial_time_using_liner_algebra>
Also, I've seen publications that are so confusing that it takes days to understand why they have a "gap"...


---

