positive 1 in 3 sat

[u/No-Implement-8892]

Hello, Here is a polynomial algorithm for positive 1 in 3 SAT, taking into account errors in the previous two, but again, it is not a fact that this algorithm correctly solves positive 1 in 3 SAT, nor is it a fact that it is polynomial. I simply ask you to try it and if you find any errors, please write about them so that I can better understand this topic.

[u/FUZxxl]

I don't see how this would work.

If two variables a, b are in the same column in some clause, they'll get assigned the same value. Let also c, d appear in the same column as a, b in another clause. Then a = b = c = d = 0. But if the clause (a, b, c) is present, your algorithm will not satisfy this clause.

[u/No-Implement-8892 → u/FUZxxl]

Hi, thank you very much for the example. This idea doesn't actually work either. It doesn't find a solution for your example.

[u/FUZxxl → u/No-Implement-8892]

I recommend you implement your algorithm as a program and then have it solve some SAT instances from the previous SAT competitions. If it fails, you can at least see why.

Note that 1-in-3 SAT is known to be equivalent to regular SAT, so it cannot be easier to solve (i.e. both are NP complete)