I've been struggling lately with a problem that was in my last complex algorithms exam, and I can't find a solution. The problem is as follows:
Half-SAT is a problem where C is a CNF boolean formula with n variables and m clauses, where m is even. We have to determine if there exists an interpretation that satisfies exactly half of the clauses. Prove Half-SAT intractability with a reduction from SAT.
Clues: A formula can have duplicated clauses It's possible to write clauses that are always true.
I'd be very grateful if you could give me any clue on how to approach this problem.