Fdtxjr

I'm not sure on how to express that in a very formal and absolutly correct way so I hope it is still understandable. I have found this algorithm and been struggling for a while proving it does or doesn't solve 3-SAT, maybe one of you can help find an example where it fails. It is inspired by this 2-SAT algorithm and is, I believe, polynomial time in the amount of variables, hence there probably exists a example where it fails. The idea is to represent higher order relations in the graph to be able to represent clauses that are made of a combination of 3 variables.

Suppose we have $m$ clauses and $n$ variables $x_1,dots,x_n$ in the usual setting, without loss of generality we can assume all the closes are made of exactly $3$ variables, that may not be distinct. A close $alor blor c$ where $a$, $b$, $c$ can be any variable or a variable negation can be rewritten in equivalent ways as
beginalign*
&lnot arightarrow (lnot brightarrow c)&&lnot (lnot brightarrow c)rightarrow a\
&lnot brightarrow (lnot arightarrow c)&&lnot (lnot arightarrow c)rightarrow b\
&lnot crightarrow (lnot arightarrow b)&&lnot (lnot arightarrow b)rightarrow c\
endalign*
using only implications and negation. From all the variables and clauses we construct a graph. For any variables $x_i$ and $x_j$ with $i<j$, then we have all the vertex labeled

• $x_i$, $x_j$, $lnot x_i$ and $lnot x_j$




• $x_irightarrow x_j$, $lnot x_irightarrow x_j$, $x_irightarrow lnot x_j$ and $lnot x_irightarrow lnot x_j$




• $lnot(x_irightarrow x_j)$, $lnot(lnot x_irightarrow x_j)$, $lnot(x_irightarrow lnot x_j)$ and $lnot(lnot x_irightarrow lnot x_j)$

We also add the vertex labeled $0$ and $1$, they represent false and true and if there is an edge $1rightarrow a$ or $lnot a rightarrow 0$, then $a$ needs to be true. The total amount of vertices is $2+2n+8nchoose 2=4n^2+6n+1$. Regarding edges, they represent logical implication and so before taking a look at clauses the graph should contain some edges such as $lnot (arightarrow b) rightarrow lnot b$, $lnot a rightarrow (arightarrow b)$ but it turns out that only the edge from $0$ to $1$ and those from $a$ to $a$ (for any vertex $a$) are needed when taking into account the algorithm. The $m$ clauses all add exactly $6$ edges mentioned above to the graph and this is the initial graph.

The algorithm try to see if there exists a vertex (that may be the composition of $2$ variables) that is strongly connected to it's negation but for now it is not possible since edges only goes from vertex of the form $lnot(arightarrow b)$ to $lnot a$ and from $a$ to $lnot a rightarrow b$ but we can combine two edges into an other one to expend knowledge that can be deduced. Suppose we have that for some vertex $a$, $b$, $c$ and $d$ the edges from $a$ to $b$ and from $c$ to $d$, then we can deduce the two implications

• $(aland c)rightarrow(bland d)$


• $(alor c)rightarrow(blor d)$

where the $land$ and $lor$ operator are the usual logical and and or. If the logical values of $(aland c)$ and of $(bland d)$ both matches with the logical value of two vertices then we add the corresponding edge to the graph, the same happen for the second line. $aland b$ is the combination of at most $4$ variables and so we can extends the tables of values it can take (as a function of the variables it is made of) which is at most $16$ different possibilities, then we can compare those the one we would obtain with any vertex of the graph that involve the same variables ($2$ by $2$, $1$ by $1$ or even the vertex $0$ or $1$). This operation can be done in constant time.

The algorithm is just an iterative application of these edges deductions, suppose we have the directed graph $G=(V,E)$ in input then a pseudo code for the algorithm is

• $Sleftarrow emptyset$


• $Rleftarrow (e,e')in Etimes E, eneq e'$


• while $Rneq emptyset$
  
  
  • $E'leftarrow emptyset$
  
  
  • for all $(a,b),(c,d) in R$
    
  
  
  • if $aland cin G$ and $bland din G$ : $E'leftarrow E' cup (aland c,bland d)$
    
  
  
  • if $alor cin G$ and $blor din G$ : $E'leftarrow E' cup (alor c,blor d)$
    
  
  
  • $Sleftarrow Scup R$
  
  
  • $Eleftarrow Ecup E'$
  
  
  • run BFS on $G=(V,E)$ and add all deduced edges that correspond to paths in $E'$
    
  
  
  • $Rleftarrow e,e' setminus S$
  
  


• return true if $(1,0)in E$ and false otherwise

The BFS line is just running BFS and adding to $E'$ an edge from $a$ to $b$ if there exists a path from $a$ to $b$, this can be optimized by remembering all visited edges from iterations to iterations of this BFS but it doesn't matter since BFS is polynomial in the number of vertex and hence of variable.

The set $S$ contains the pair of edges we have already tried to combine and $R$ is the set of new pair of edges we could combine, since we iterate until we don't have anything else to combine, the cardinality of $S$ is strictly increasing at each iterations and so the worst case is an increase by one at each steps. The amount of edges of the graph is at most $|V|(|V|-1)=O(n^4)$ and so the amount of combination of two different edge we can have is $O(n^8)$ and this is the complexity of the number of time we do any of the line inside the inner and outer loop, hence I think that this algorithm runs in polynomial time.

The return condition is equivalent to the one of having a vertex and its logical negation strongly connected, indeed if for some vertex $a$ we have $arightarrow lnot a$ then we combine it with the edge $lnot arightarrow lnot a$ to get $1=alor lnot a rightarrow lnot a lor lnot a = lnot a$, if we also have $lnot a rightarrow a$, we can combine it with $lnot arightarrow lnot a$ to get $lnot a = lnot a land lnot a rightarrow lnot aland 0 = 0$ and hence, combining the two we can deduce a path from $1$ to $0$.

Here I list some of the things the algorithm does or preserves. First observe that there should be a lot of edges in the graph in the beginning such as $arightarrow (lnot arightarrow b)$ since they are tautologies, those edges are always deduced at the first iteration of the algorithm since we can combine the two edges $b rightarrow b$ and $0rightarrow 1$ with $land$ to get that $0rightarrow b$ and then we can combine this one with $arightarrow a$ using $lor$ to get that $arightarrow (lnot arightarrow b)= alor b$.

If there is an edge from $1$ to $arightarrow b$ then the later is considered true and we would like to add an edge from $a$ to $b$ (which are in the graph), this is done combining the edge with $arightarrow (lnot arightarrow b)$ using $land$ to get that $aland 1 = arightarrow b=(lnot arightarrow b)land (arightarrow b)$, the converse is also true, if we have an edge from $a$ to $b$ and they are either variable or negation of variable, then combining them using $lor$ gets us $1rightarrow (arightarrow b)$.

At the end of the while loop (or begining) it is always true that if we have an edge from any vertex $a$ to $b$, then we also have an edge from $lnot b$ to $lnot a$, indeed this property is true in the begining of the algorithm and if we combine $arightarrow b$ and $crightarrow d$, then we also combine $lnot brightarrow lnot a$ and $lnot drightarrow lnot c$ to get the two wanted edges.

If we have the two clauses $(alor blor c)land(lnot alor d lor e)$, then there will be an edge from $(lnot brightarrow c)$ to $(lnot drightarrow e)$, this is seen easily from the initial edges plus the BFS. In particular $(alor blor c)land(lnot alor b lor c)$ will add an edge from $lnot b$ to $c$.

Since we don't add any implication that may be false, then of course if the algorithm returns false, then the 3-SAT was not satisfiable so the only thing to prove or disprove is that if the algorithm return true, then the 3-SAT has solution. My guess is that there is probably a example of 3-SAT that is not satisfiable where my algorithm return true but I failed to find one.