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?