4
$\begingroup$

I am trying to understand why it is not possible to use implication graphs, that work to solve $2SAT$, to solve $3SAT$ or $kSAT$ in general.

Intuitively I think its because implication extends from one variable from one variable to another, with a fixed status for each variable. In $2SAT$ this works for each clause to create implications that solve the clause. In $3SAT$ a similar implication is not possible. At first it appears that we can create an implication for $(a \lor b \lor c)$ like this $(\lnot a,\lnot b) \to (c)$. The issue is obvious, the implications are not enough since it cannot cover the case when $a$ or $b$ is true and the other false.

Is this correct? Or is there another reason?

I tried google and this site, but I couldn't find anything which explains why this method to solve $2SAT$ in polynomial time won't work for $3SAT$. I know it can't, otherwise $3SAT$ wouldn't be NP-Complete, but I'd like to understand why.

$\endgroup$
0
$\begingroup$

It might be helpful to consider the related problem in resolution first. Briefly, if we consider 2-SAT, the clauses all contain only two literals, so the resolvent of those two clauses still has at most two literals. If we go to 3-SAT, the clauses have three literals, so the resolvent of two such clauses can contain four literals, not three. Things can grow exponentially from there as longer and longer clauses build up and are resolved together.

The situation is analogous with implication graphs. When we use implication graphs on 2-SAT, longer implications simply grow linearly, whether we go backwards or forwards. So we can string implications together in a linear chain and look for contradictions in linear time in the implication graph.

Now let's go back to our attempts to use implication graphs on 3-SAT. Converting $(a \lor b \lor c)$ to an implication yields $((\neg a \land \neg b) \rightarrow c)$ (and several other expressions we can ignore for now). What happens if we try to connect long chains of these? Rather than nice linear chains, we get an exponential explosion as we work backward. So we start with our first clause $(\neg a \land \neg b) \rightarrow c$. What about $\neg a$ and $\neg b$? Each of those could have another clause leading to it, for example $(p \land q) \rightarrow \neg a$ and $(r \land s) \rightarrow \neg b$. Those two clauses now have potentially four antecedents: $p, q, r, s$. And so on.

Things get worse as we consider multiple implications leading to the same literal. In the 2-SAT case, two lines of implications simply merge onto the one literal: linearity is preserved. Not so for 3-SAT: we now have multiple trees of implications and we may have to search all of them.

And finally contradictions. Finding a contradiction is easy in 2-SAT: we simply look for a circularity which contains a literal and its negation. For example, consider $a \rightarrow \neg a$ and $\neg a \rightarrow a$. This is a simple cycle we can traverse, and again this can all be done in linear time. This all breaks down in 3-SAT. Even a simple extension of our example breaks down. Consider $(\neg a \land q) \rightarrow a$ and $(a \land q) \rightarrow \neg a$. We have no contradiction if $q$ is false.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.