I thought about an algorithm that I think solves 3 - SAT with high probability in polynomial time (DEA, the dual expression algorithm, see attachment). I have not been able to prove the polynomial time without any doubt, but arguments based on Markov chain theory indicate that fact. I would appreciate any suggestions. Is anyone interested in testing this algorithm?
Article An Efficient Algorithm for 3-SAT
Before I could complete reading the paper you have linked here, I stumbled on this: In your DEA algo (pages 2,3, Section 3), you say you flip _one_ zij, but then this is not possible because if you flip any one of xi or xj, then two of the z variables will flip in an unsatisfied clause. e.g. Take xiVxjVxk unsatisfied. That means all three xi, xj, xk are false. Similarly zij, zik, zjk are all false. Flip xi: then zij and zik will flip, both. At the same place you also claim that corresponding to an unsatisfied clause xiVxjVxk, at most one z variables is satisfied -- but the z variables are such that two of them simultaneously can be satisfied, not one of the three alone. The same considerations (_dependence_ of variables!) will also spoil the simplistic probability claims there.
Thank you for your answer to my question from ResearchGate. Please read the last version of my article (SAT13.pdf posted on ResearchGate on my profile).
You assume that we update the x_i assignments every time we find a consistent active chain of dual variables. That is a false assumption.
We work with a solution path (which I also call the active chain of dual variables) through the 3 - CNF clauses, and this active chain of dual variables is formed of 2-CNF clauses, only one for each 3 -CNF clause. At any stage of the algorithm, this chain can have length N (the number of 3-CNF clauses) or less than N, this chain will grow in length, or decrease, depending on whether Test2CNF tells us that the current active chain of dual variables is consistent or not. I emphasize that we do not seek the solution in terms of the original variables unless we have all the 3-CNF clauses solved. That is the whole point, each state of the active chain of dual variables represents a whole class of x_i assignments. That is why in a space of 2^n objects, we can find a certain object (the solution) in polynomial time with sufficiently high probability. My algorithm, if anything, is not simplistic, but it requires attention (and I do agree that it needs more work).
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics
- Probability
- Probability Theory