Is 3-CNF to 2-CNF generally possible (or in particular)?
No.
First of all, if there is a polynomial-time algorithm translating 3-CNF formulas to 2-CNF formulas preserving satisfiability, then P=NP. This is because the set 2-SAT of satisfiable 2-CNF formulas has a polynomial-time algorithm, but 3-SAT is NP-complete.
$\DeclareMathOperator{\maj}{maj}$Unconditionally, it is not too hard to show that any 2-CNF defines a "bijunctive" relation. A relation $R\subseteq \{0,1\}^n$ is bijunctive if it has the majority polymorphism, meaning that if $x,y,z\in R$ then $(\maj(x_1,y_1,z_1),\dots,\maj(x_n,y_n,z_n))\in R,$ where $\maj$ is the ternary majority function. the relation defined by $\neg A+\neg B+C$ is not bijunctive because $\maj((1,0,0),(0,1,0),(1,1,1))=(1,1,0).$ So it cannot be expressed as a conjuction of two-variable disjunctions. See https://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem for more.
Related videos on Youtube
thwd
I make stuff that grows on sockets. Concurrency is my main field of interest. I prefer expressions over statements, breaking abstractions in favor of clarity.
Updated on January 25, 2020Comments
-
thwd almost 4 years
Consider the logic formula (where · denotes logical and/conjunction):
$C \leftrightarrow A · B$
Using the Tseytin transformation we arrive at an equivalent CNF (where + denotes logical or/disjunction and ¬ denotes negation):
$(\lnot A + \lnot B + C) · (A + \lnot C) · (B + \lnot C)$
Is this formula further reducible/inflatable to 2-CNF, i.e. "breaking up" the 3-term disjunction into n 2-term disjunctions?