1
$\begingroup$

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) ∧ (...)}$

$\endgroup$
2
  • $\begingroup$ Uni. We've been told to assume it is a NP-complete problem and try to prove it. The definition above was a little confusing, I've made it more accurate and easier to understand. $\endgroup$ Dec 7, 2022 at 20:33
  • $\begingroup$ I suggest you keep working on it. What are the criteria for the reduction to be correct? Does your example meet those criteria? If not, can you fix it up? FYI, you might receive some resistance to questions that post an exercise and ask for the solution. $\endgroup$
    – D.W.
    Dec 7, 2022 at 20:42

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The input doesn't have to be a 3CNF. $\endgroup$ Dec 8, 2022 at 16:38
  • $\begingroup$ @YuvalFilmus Indeed, you are right! $\endgroup$
    – Nathaniel
    Dec 8, 2022 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.