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

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?

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.