Is 3-CNF to 2-CNF generally possible (or in particular)?

1,233

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.

Share:
1,233

Related videos on Youtube

thwd
Author by

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, 2020

Comments

  • thwd
    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?