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:
- 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”.
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
