1
$\begingroup$

Can we assume that each clause in 3SAT contains at least one positive literal? That is, there is no clause with all negative literals (but it is fine that there is a clause with all positive literals).

$\endgroup$
  • 4
    $\begingroup$ What do you mean by "Can I assume it?", the 3CNF: $\overline{x}\lor\overline{y}\lor\overline{z}$ is satisfiable (i.e. it is in 3SAT), but does not satisfy your assumption. $\endgroup$ – Ariel Dec 14 '17 at 21:33
1
$\begingroup$

You can assume this, in the sense that you can transform a 3SAT problem into this form with only polynomial size overhead. The idea is to to a Tseitin Transform on one variable in each clause with 3 negative literals.

So if you wanting to eliminate $\lnot x$, you introduce a fresh variable $y$ and add the clauses $ x \vee y$ and $\lnot y \vee \lnot x$. This is basically just encoding $\lnot x \iff y$. You can add a third dummy positive variable to ensure that these clauses also are not all negative.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Perhaps you'd like to work out your gadget so that it actually conforms to the spec. $\endgroup$ – Yuval Filmus Dec 14 '17 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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