1
$\begingroup$

I already know that SAT and 3-SAT are NP-complete. If in 3-SAT the Boolean expression should be divided to clauses,such that every clause contains at most (in the original problem it says exactly) three literals would it still be NP-complete?

I think the answer is yes but I'm not sure of my solution. I think the reduction will remain pretty much the same. We'll use SAT. For the clauses that contain 1,2 or literals we don't change anything. For the clauses that contain more that 3 literals we turn them into clauses with 3 literals like we did in the original 3-SAT.

Are my thoughts correct or am I missing something?

Improve this question
$\endgroup$
3
  • $\begingroup$ Your reduction is in the wrong direction. You are reducing your problem to 3SAT, thus showing that it is in NP; but that is obvious. Presumably you wanted to prove that your problem is NP-hard, in which case you want to reduce 3SAT to your problem. $\endgroup$
    – Yuval Filmus
    Dec 9, 2022 at 16:45
  • $\begingroup$ My goal is to find a polynomial-time reduction from SAT to 3-SAT'(not the original 3-SAT) . The reduction is a polynomial-time computable function f that takes a clausal formula φ and yields a clausal formula φ′ with maximum 3 literals per clause. Am I saying something wrong? $\endgroup$
    – Hjm
    Dec 10, 2022 at 8:40
  • $\begingroup$ You can instead reduce 3SAT to 3SAT'. As a reduction, you can use the function $f(\phi) = \phi$. $\endgroup$
    – Yuval Filmus
    Dec 10, 2022 at 11:26

1 Answer 1

Reset to default
1
$\begingroup$

Yes, it would.

To make this answer self-contained, here is a sketch of how the transformation works.

Take any SAT problem in CNF. Suppose you have a clause that is more than three literals in size. Let's say it's four.

$$x_1 \vee \neg x_2 \vee x_3 \vee \neg x_4$$

Introduce a fresh variable $y$. Then this clause is equivalent to the conjunction of two clauses:

$$\left(x_1 \vee \neg x_2 \vee y\right) \wedge \left(x_3 \vee \neg x_4 \vee \neg y\right)$$

The proof is simple, because this is just the resolution rule. Using this transformation and a lot of fresh variables, you can turn any clause into the conjunction of linearly-many three-variable clauses.

Since, any SAT problem can be turned into this 3SAT variant, it follows that this variant is NP-hard. It is also in NP since a valid variable assignment is a certificate checkable in polynomial time. Therefore it is NP-complete.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In order to show that ≤3SAT is NP-hard, it suffices to reduces 3SAT to ≤3SAT. You can use the identity function as a reduction. $\endgroup$
    – Yuval Filmus
    Dec 9, 2022 at 16:44

Your Answer

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

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