4
$\begingroup$

This question is motivated by my answer to another question in which I stated the fact that both Betweeness and Non-Betweeness problems are $NP$-complete. In the former problem there is a total order such that the betweeness constraint of each triple is enforced while in the later problem there is a total order such that the betweeness constraint of each triple is violated.

What is the complexity of the following 3SAT variants?:

3SAT_1={($\phi$): $\phi$ has an assignment that makes every clause false}

3SAT_2={($\phi$): $\phi$ has an assignment such that exactly half of the clauses are true and the other half is false}

$\endgroup$
10
$\begingroup$

3SAT_1 is easy, and a variant of 3SAT_2 is NP-complete. My guess is that 3SAT_2 is also NP-complete. Update: my guess is proved below.

Let $C = x\lor y\lor z$ be a clause. Then $\lnot C = \lnot x \land \lnot y \land \lnot z$. An assignment makes every clause of $\phi$ false if it makes all their negations true. The conjunction of the negation of all clauses is just a big conjunction. A conjunction is satisfiable if and only if it does not contain a variable and its negation. So 3SAT_1 is in P (in fact it's in AC$^0$).

The variant of 3SAT_2 asks whether $\phi$ has an assignment that makes exactly $8/9$ of the clauses true. This is clearly in NP. To reduce 3SAT to this variant, take the formula $\phi$, and for each clause $C$ in $\phi$ add the eight clauses $$(x_C \lor y_C \lor z_C) \land \cdots \land (\lnot x_C \lor \lnot y_C \lor \lnot z_C).$$ In any assignment, exactly seven of these are correct. In total we have $9|\phi|$ clauses. Of the $8|\phi|$ that we added, exactly $7|\phi|$ are always correct. Hence $\phi$ is satisfiable if and only if in the new formula one can satisfy exactly $8|\phi|$ constraints, which are $8/9$ of its clauses.

Update: Here is a reduction from 3SAT to 3SAT_2 itself. Given a formula $\phi$, consider two cases. The first case is when we can falsify all clauses in $\phi$ at once. As shown above, in this case each variable appears only positively or only negatively, and so setting it appropriately, the formula is satisfiable. Otherwise, add $|\phi|$ clauses of the form $x \lor y \lor z$, where $x,y,z$ are new variables. In any assignment either all of these are satisfied, or all are not satisfied. Since the original clauses cannot be all falsified at once (by assumption), the new formula can be half-satisfied if and only if the original one is satisfiable.

$\endgroup$
  • $\begingroup$ Thanks Yuval. I think there are gaps in your reduction to 3SAT_2. For instance, case 1 does not guarantee the 50-50 requirement. In case 2, Are you introducing $3| \phi|$ new variables? If this is the case, I think your claim "In any assignment either all of these are satisfied, or all are not satisfied" does not hold. $\endgroup$ – Mohammad Al-Turkistany Apr 19 '12 at 11:03
  • $\begingroup$ I think your answer for 3SAT_1 is correct and it is in $P$. $\endgroup$ – Mohammad Al-Turkistany Apr 19 '12 at 12:07
  • $\begingroup$ In case 1 you already know the answer so you pick some 3CNF formula that you already know is in 3SAT_2, say $(x\lor y\lor z)\land(a\lor b\lor c)$. In case 2, I introduce only three new variables, $x,y,z$. The clause $x\lor y\lor z$ is repeated $|\phi|$ times. $\endgroup$ – Yuval Filmus Apr 20 '12 at 5:35
  • $\begingroup$ Don't you agree that all those $|\phi|$ clauses are just one clause even if you repeat them infinite number of times?. $\endgroup$ – Mohammad Al-Turkistany Apr 20 '12 at 12:33
  • $\begingroup$ No, there are the same clause repeated many times. If you want, you can redefine 3SAT_2 to rule out repeating clauses, but unless you have, it's perfectly legal. $\endgroup$ – Yuval Filmus Apr 21 '12 at 6:57

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.