# Is checking whether a 3-SAT is satsifiable if and only if every clause has at least 2 or all three literal set to true an NP-complete problem?

I want to know if checking whether a 3-SAT is satsifiable if and only if every clause has at least 2 or all three literal set to true NP-complete?

It seems similar to Exact-3SAT but it differs from it as the version of this problem which we'll call Exact2or3-3SAT ,where all literals are positive is trivial as its always true .That's why I want to know if its NP-complete or not ?

• I can't understand your question. Can you edit it to break it down into smaller sentences? I can't understand what two propositions are being related by the "if and only if". I suggest you define the problem that you are interested in, by listing the inputs to the algorithm and the desired output.
– D.W.
Jan 28, 2023 at 17:29

It is not currently known whether your problem is $$\mathsf{NP}$$-complete, but it can definitely be solved in polynomial time since it can be reduced to 2-SAT. If we assume $$\mathsf{P} \neq \mathsf{NP}$$, then your problem is not $$\mathsf{NP}$$-complete.
The reduction is as follows: a clause $$(\ell_1, \ell_2, \ell_3)$$ of your problem is satisfied iff there does not exist a pair of distinct literals $$\ell_i, \ell_j$$ that are both false. Equivalently, for all pairs $$\ell_i, \ell_j$$ of literals you must have that at least one of $$\ell_i$$ and $$\ell_j$$ is true.
This shows that you can replace each clause $$(\ell_1, \ell_2, \ell_3)$$ with: $$(\ell_1 \vee \ell_2) \wedge (\ell_1 \vee \ell_3) \wedge (\ell_2 \vee \ell_3),$$ to obtain an equivalent 2-SAT instance.
As a note, there is also a straightforward reduction from 2-SAT to your problem: add a new variable $$x$$ and replace each 2-SAT clause $$(\ell_1 \vee \ell_2)$$ with $$(\ell_1, \ell_2, x)$$.