9
$\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$

2 Answers 2

3
$\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$
0
$\begingroup$

I do not fully agree with the answer.
It seems to me that the trick that works for 2SAT, is that we have:

(a∨b) ∧ (c∨d) ↔
(¬a→b) ∧ (¬b→a) ∧ (¬c→d) ∧ (¬d→c)

So we keep the ∧ operator between a finite number of elements.

The implication graph is only a trick to change the variables and the operators without increasing the number of variables, and with a small increase of the number of operators.

With 3 Clauses in 3SAT, whatever change of variable we do, we will always have some cases in which, we increase significantly the number of operators.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .