I am studying algorithms and there is a question in CLRS called the Half-SAT problem

We are given a 3-CNF formula with n variables and m clauses where m is even. We wish to determine whether there exists a truth assignment to the variables of f such that exactly half the clauses evaluate to zero and the other half to 1. Prove that the half 3-SAT problem is NP-Complete.

What is to stop me from taking any input f to 3-SAT and adding m clauses (y or y or y) where y is not in the original m clauses. The transformation of input and output is clearly polynomial time.

And, given a solution to 3-SAT, there must be a satisfying solution to Half-SAT (the solver sets y to false). If there is not a solution to 3-SAT this means that one of the original m clauses is not satisfied these clauses are disjoint from the new clause, so either m - 1 or 2m - 1 clauses are True.

Yet all the solutions online are more complicated which makes me think I am missing something obvious.

  • 5
    $\begingroup$ Your reduction needs to also have the property that a solution to the constructed Half-SAT instance implies a solution to the original 3-SAT problem -- but this isn't necessarily the case, since it could be that the Half-SAT solution involves setting the new variable $y$ to true and letting all other clauses be false. $\endgroup$ – j_random_hacker Apr 14 at 6:06
  • 1
    $\begingroup$ What @j_random_hacker wrote is true. Nevertheless, it is easy to check whether there is an assignment that makes all the original clauses false (this holds if and only if no variable occurs both positively and negatively in the CNF), and it turns out that in this case the original CNF is always satisfiable. Thus, the given reduction actually works, if it is augmented with this extra polynomial-time check. Of course, all this assumes that it is legal to have repeated clauses in the CNF (but the other linked solution also assumes this). $\endgroup$ – Emil Jeřábek Apr 14 at 13:56
  • $\begingroup$ Yes it is more subtle than I thought. I need to enforce that Half-SAT solution implies SAT solution. But as @j_random_hacker has said I can have a solution to Half-SAT but not SAT. So I need to add an additional contradictory clauses (y or y not) and m + 1 clauses, I will update my question and answer. $\endgroup$ – Anthony O Apr 14 at 15:53
  • $\begingroup$ @EmilJeřábek: Interesting observation about making all original clauses false, but IIUC, your reasoning by itself is enough to make the OP's reduction go through, and no "runtime" polynomial-time check actually needs to be computed? I.e., any given 3-SAT instance either is or is not able to reach all-clauses-false, and in both cases the solution to the constructed Half-SAT instance agrees with the solution to the 3-SAT instance, so we don't need to care which case we are in. $\endgroup$ – j_random_hacker Apr 15 at 2:34
  • $\begingroup$ @j_random_hacker Oh, yes, you are right. $\endgroup$ – Emil Jeřábek Apr 15 at 4:43

As mentioned in the comments, this reduction is incorrect because it is necessary to have equivalence. While we may have 3-SAT => Half-SAT we do not have !3-SAT => !Half-SAT or Half-SAT => 3-SAT (the contrapositive). A proper reduction would need to do something like so:

Add m + 1 clauses (y or y or y)

Add a contradictory clause (y or not y)

Now exactly half of the clauses are True iff there is a solution to 3-SAT.

  • $\begingroup$ Well, Emil Jeřábek's comment shows that the reduction actually is correct after all -- but any claim that the reduction is correct needs to include a proof of that fact along the lines Emil gave. $\endgroup$ – j_random_hacker Apr 15 at 11:31

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