[Solved]: Showing NP-hardness of HALF-SAT

Problem Detail: 

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:

1. HALF-SAT is probably not $\in$ NP, at least in no verifiable way I can think of (not really relevant to the question)
2. 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
3. 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".

Asked By : Sebastian Graf

Answered By : Yuval Filmus

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14165