Definitions:
SAT is the problem "Given a propositional logic statement, does the statement have an assignment of its variables that result in the statement being true".
3-SAT is a SAT problem, written as clauses with 3 variables or less. For example ((A or B or C) and (not B or not C))
has 2 clauses. A
, B
and C
are boolean variables; "or
" and "and
" are the standard logical operators. This problem has at least one solution (A, B, C) = (true, false, true)
.
2-SAT is a SAT problem, written as clauses with 2 variables or less.
We can reduce 2-SAT to the problem of finding a cycle in a directed graph: We can create a vertex for each variable (and its negation). We write each clause ((A) or (B))
in implication form: ((A) or (B)) <=> ((not (not A)) or (B)) <=> ((not A) implies (B))
. We add a directed edge for each "implies" clause. The 2-SAT problem will be satisfied if and only if for all variables X
, vertices (X)
and (not X)
are not contained in a cycle. (Equivalently, there is a path from (X)
to (not X)
and a path from (not X)
to (X)
if and only if there is a contradiction - that is, if the 2-SAT problem is not satisfied.)
Can a 3-SAT clause be "directly" (defined in [3]) reduced to a 2-SAT problem?
[1] 2-SAT is equivalent to "for some X, does the implication graph contain both paths from (X)
to (not X)
and from (not X)
to (X)
?
[2] In other words, a 2-SAT problem is satisfied if and only if 2 vertices in its implication graph contradict (are in the same cycle).
How, then, can there be a "direct" reduction from a 3-SAT clause to 2-SAT?
[3] If there's a "direct" reduction from a 3-SAT clause to 2-SAT, then, for each clause D = (A or B or C)
, there will exist 3 vertices A
, B
, C
in the 2-SAT implication graph such that the clause D
is satisfied if and only if (not ((not A) and (not B) and (not C)))
(which falsifies the clause).
[4] There are 3 variables involved there ([3]) in the satisfaction.
[5] A 2-SAT problem is satisfied, or not, based on 2 vertices ([2]).
[6] You can't encode "unsatisfy if and only if 3 variables contradict" into directed edges ("directly"). (A 2-SAT problem could have multiple pairs of contradicting vertices; each contradiction corresponds to a pair of vertices. You can't "fit" 3 "into" a pair.)
[7] Given [6], if a 3-SAT clause can be "directly" reduced to 2-SAT, then, it must not be one-to-one with the variables.
Therefore, a 3-SAT clause cannot be "directly" reduced to 2-SAT.