How to reduce 3SAT to TwoOrMoreSAT?

Question

I want to prove, that 2OrMoreSAT is NP-complete. It's defined as follows:

A formula is considered strongly satisfiable if there exists a model such that two or more different literals in every clause evaluate to true.

$\textit{2OrMoreSAT} = \{\langle \phi' \rangle \mid \phi' \text{ is a boolean formula in CNF which is strongly satisfiable} \}$

I want to solve this by reducing 3SAT to 2OrMoreSAT. My first thought was to duplicate all of the literals in a clause, which would ensure 2 or more literals being true - but I don't really know how to limit the literals after. Say ${\phi}$ ∈ 3SAT and ${\phi = X ∨ Y ∨ Z}$, then ${\phi'}$ could look something like this ${\phi' = (X_1 ∨ X_2 ∨ Y_1 ∨ Y_2 ∨ Z_1 ∨ Z_2) ∧ (...)}$

Answer 1

As pointed out by Yuval Filmus in the comments, I assumed there that the formula had to be in 3CNF, which is not necessarily the case. However, I will let my answer, maybe it can still help.

I may be wrong, but I think this problem is in $\mathsf{P}$, there is a reduction to $\texttt{2SAT}$.

Consider a clause $C = (x\lor y \lor z)$. From this clause, define:

$$\phi_C = (x\lor a) \land (y \lor b) \land (z\lor c) \land (x\lor \overline{b}) \land(x\lor \overline{c}) \land(y\lor \overline{a})\land (y\lor \overline{c})\land (z\lor \overline{a}) \land(z\lor \overline{b})$$

Then I claim that $C$ is satisfiable with at least two true litterals if and only if $\phi_C$ is satisfiable, and moreover, the truth values of $x$, $y$ and $z$ are the same in both truth assignments.

The idea is that $a\equiv y\land z$, $b\equiv x\land z$ and $c\equiv x\land y$.

Now if $\varphi = \bigwedge\limits_{i=1}^n C_i$ is a formula in 3CNF, then $\psi = \bigwedge\limits_{i=1}^n\phi_{C_i}$ is a formula in 2CNF, and $\varphi$ is satisfiable with at least two true litterals per clause if and only if $\psi$ is satisfiable (this is due to the fact that in the previous claim, the truth values of $x$, $y$ and $z$ are the same, so a satisfying truth assignment does not change values between clauses).

Since this construction is done in polynomial time, $\texttt{2orMore3SAT}\leqslant_m^p\texttt{2SAT}$, which is known to be in $\mathsf{P}$.

What would be a $\mathsf{NP}$-complete problem, though, is the following problem:

Input: a boolean formula $\varphi$ in 3CNF.

Question: is $\varphi$ satisfiable with exactly two true litterals per clause?

The reduction from $\texttt{3SAT}$ transforms a clause $C = (x\lor y \lor z)$ into: $$\phi_C = (x \lor a \lor b) \land (y \lor c \lor d) \land (z\lor e \lor f) \land (a \lor c\lor e)$$

• if $C$ is satisfied, distinguish depending on the number of true litterals:

  • if exactly one litteral is true, say $x$ WLOG, then assign $b, c, d, e$ and $f$ to true and $a$ to false;
  • if two litterals are true, say $x$ and $y$ WLOG, assign $a, c, e, f$ to true and $b, d$ to false;
  • if all three litterals are true, assign $a, c, f$ to true and $b, d, e$ to false.

  In all cases, $\phi_C$ is satisfied with exactly two true litterals per clause, and the truth values of $x$, $y$ and $z$ are unchanged.

• Conversely, if $\phi_C$ is satisfied with exactly two true litterals per clause, then exactly two among $a$, $c$ and $e$ are true, say $a$ and $c$. That means that $z$ and $f$ are true, so $C$ is satisfiable. Other cases are similar.

The rest of the reduction is similar to the problem above.