4 ms·
It 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,
by cyrus_ 16y ago
It 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 https://github.com/anjlab/sat3.
- The author references no prior work, just review papers on the problem itself.
- deleted 16y ago[deleted]
- wnoise 16y ago> - It not only tells you whether the formula is satisfiable or not, but gives you the satisfying values. Any yes/no NP solver can be turned into one that does this with polynomial overhead. After finding there is a solution, you ask it the similar problem "does this have solution with the first bit set to true?", then "does this have a solution with the first bit set to <answer to previous question> and the second bit set to true?", and so forth until you've identified all bits.