NP-Hardness of Half-SAT (at least half clauses)

Question

I'm solving Problem 14.14 of What can be computed?.

14.14 Consider the computational problem HALFSAT defined as follows. The input is a Boolean formula B in CNF. If it is impossible to satisfy at least half of B’s clauses, the solution is “no”. Otherwise a solution is a truth assignment that does satisfy at least half of B’s clauses. For example, the input “(x1 OR NOT x2) AND (x2) AND (NOT x1)” is a positive instance, because the truth assignment “x1=1,x2=1” satisfies two of the three clauses and is therefore a positive solution. Prove that HALFSAT is NP-hard.

There some variants of half-SAT in this community, but I couldn't find the way of reduction to this version of HALF-SAT problem.

Is there any suggestion to solve this problem?

Answer 1

If all clauses must be non-empty, then your problem isn't NP-hard, since every CNF can be half-satisfied: a random assignment satisfies at least half of the clauses in expectation, and so some assignment satisfies at least half of the clauses.

If clauses are allowed to be empty (unsatisfiable), then there is an easy reduction from SAT: given an instance of SAT with $m$ clauses, add $m$ unsatisfiable clauses. The new instance is half-satisfiable iff the original one is satisfiable.