Showing NP-hardness of HALF-SAT Yesterday I wrote my undergraduate exam in complexity theory. I had to leave off one question, which bugs me since then. Consider:
$$ HALF-SAT = \{ \varphi \mid \varphi \text{ is a formula which is satisfied by at least half of all assignments }\} $$
I'd like to know how I can prove NP-hardness.

FWIW, here's what I figured out:


HALF-SAT is probably not $\in$ NP, at least in no verifiable way I can think of (not really relevant to the question)
SAT $\preceq$ HALF-SAT doesn't work, at least not by just adding clauses with new variables, doesn't change satisfiable-assignments/arbitrary-assignments ratio
TAUT $\preceq$ HALF-SAT via $\varphi \mapsto \varphi \wedge x_{new}$, but that's coNP-hardness (together with NP-hardness this further lets me assume 1., intuitively)


And no, this has nothing to do with the problem you find via googling "HALF-SAT".
Hint: Take a new variable $x$ and add it to all clauses. This shows that HALF-SAT' is NP-hard, where HALF-SAT' differs from HALF-SAT by strengthening "at least half" to "more than half". HALF-SAT is similar.

The $P$-closure of HALF-SAT' (and HALF-SAT) forms the complexity class $PP$.