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
$\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$ Apr 27 '20 at 22:31

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.