0
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 28, 2023 at 17:29

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$
0

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.