Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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 ?
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)$.
