How is this reduction of 3-SAT to Half-SAT not valid?
As mentioned in the comments, this reduction is incorrect because it is necessary to have equivalence. While we may have 3-SAT =&gt; Half-SAT we do not have !3-SAT =&gt; !Half-SAT or Half-SAT =&gt; 3-SAT (the contrapositive). A proper reduction would need to do something like so:
Add m + 1 clauses (y or y or y)
Add a contradictory clause (y or not y)
Now exactly half of the clauses are True iff there is a solution to 3-SAT.