2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

No, a 3-CNF clause cannot be directly reduced to a 2-CNF clause.

2-SAT solutions all have the median property: You can take any three solutions, take the majority value of each variable and produce a fourth solution. If a Boolean formula has three satisfying assignments that together do not have this property, then that formula cannot be represented as a conjunction of 2-CNF clauses. As an example $(x_1 \lor x_2 \lor x_3)$ has among its satisfying assignments 100, 010 and 001. Taking the majority value of each variable produces 000, which is not a satisfying assignment. So $(x_1 \lor x_2 \lor x_3)$ cannot be equivalently represented as a 2-CNF clause.

$\endgroup$
1
  • $\begingroup$ Was there something wrong with my proof? $\endgroup$ Commented Apr 27, 2020 at 22:31

You must log in to answer this question.

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