CNF-SAT reduction problem variant

Question

I'm aware of the Cook-Levin theorem. I've also seen how to reduce SAT to 3-CNF SAT to show that the latter is also NP-Complete. The following problem is a variant, though, and I'm not sure how to proceed:

Define 1/3-CNFSAT as follows: given a set of boolean variables and clauses in Conjunctive Normal Form, (this isn't 3-CNF SAT, as each clause may contain an arbitrary number of variables), does there exist a set of assignments to each variable such that exactly one-third of the clauses are satisfied?

Prove via reduction that 1/3-CNFSAT is NP-complete.

My initial thought process: Reduce CNF-SAT to 1/3-CNFSAT (Given: since any SAT formula can be reduced to CNF form, CNF-SAT is NP-complete).

So I was thinking, given some formula in CNF form, which contains C number of clauses, I was thinking we could add to it an additional 2C clauses, all of which are unsatisfiable. Then CNF-SAT would be satisfiable IFF 1/3-CNFSAT would be satisfiable.

Please let me know if my thoughts thus far are incorrect.

My problem now is how to come up with an additional 2C clauses all of which are false, and express each of them in CNF form. Obviously, something like the following clause would be inherently false:

(x1 AND ~x1)

But if I were to express it in CNF form, I'd have to do something like the following:

(x1 OR x1) AND (~x1 OR ~x1)

Or, even more simply:

(x1) AND (~x1)

But the problem is, only one of the above clauses is false for some given boolean assignment to x1. So, how do I come up with 2C false clauses and express them all in CNF form?

I hope this question makes sense. Thanks for help.

Answer 1

1/3-CNFSAT is very much similar to HALF-SAT, where instead of satisfying exactly half of the total number of clauses you are satisfying exactly one third of it. So the reduction from 3SAT is also quite similar. We reduce 3SAT instance, $\phi$, to a 1/3-CNFSAT instance as follows.

Let $z$ be a new variable not in $\phi$. Let there be $m$ clauses in $\phi$. We add $(z \lor \lnot z)$ and $2m+2$ copies of $(z)$ to $\phi$. In every exactly 1/3-satisfying assignment $z$ must be false.

Let $\phi \land (z \lor \lnot z) \land (z) \land (z) \land ... (2m+2) $ copies $...\land (z) = \phi'$. The following claim is easy to prove.

Claim: $\phi$ is satisfiable iff $\phi'$ has exactly 1/3rd satisfiable clauses.

Therfore 3SAT $\leq_P$ 1/3-CNFSAT, and hence 1/3-CNFSAT is NP-complete.