# 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:

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

• What is the problem exactly? Are you given an arbitrary SAT instance and asked to determine if it belongs to HALF-SAT? Or are you given a HALF-SAT instance and asked to determine if a solution exists? The answer to the second problem is always 'yes', and a satisfying assignment can be found with a randomized algorithm. – Austin Buchanan Sep 3 '13 at 17:54
• If I understood correctly, it's neither. I want to show that the decision problem HALF-SAT is NP-hard and tried so with karp reduction. $\varphi$ is an arbitrary (well-formed, iirc) formula, which is satisfied by (at least) half of all possible assignments. I should probably exchange SAT for 3-KNF to make the distinction clearer. If this helps, I'll edit the question accordingly. – Sebastian Sep 3 '13 at 18:13

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

• Ahh, so instead of going with what I outlined as 2., we don't add clauses rather than extend the existing ones. Suddenly it makes sense. Facepalm. – Sebastian Sep 3 '13 at 20:11
• But assuming that my reduction 3. is valid, how can HALF-SAT be NP-complete (PP $\subseteq$ NP) while also being coNP-hard? – Sebastian Sep 3 '13 at 20:15
• The inclusion is in the reverse direction: NP$\subseteq$PP. – Yuval Filmus Sep 3 '13 at 20:38
• What does phrase '$P$ closure' mean? – Bread Winner Jul 13 '19 at 14:42
• Problems polytime-reducible to HALF-SAT'. – Yuval Filmus Jul 13 '19 at 15:03

A possible reduction from SAT is the following. Assume given formula $\varphi$ has variables $x_1,\dots,x_n$ we map $\varphi$ to $$(\varphi\land y)\lor\left(\overline y\land\bigvee_{i=1}^nx_i\right).$$

1. If $\varphi\notin\textrm{SAT}$, then the left part is always false. The right part is satisfiable for $y=0$ getting $2^n-1$ solutions. Hence $f(\varphi)\notin\textrm{HALF-SAT}$.
2. If $\varphi\in\textrm{SAT}$, then for assignments setting $y=1$ we get $c>0$ satisfying assignments for the left part. If $y=0$ we still get the $2^n-1$ many satisfying assignments. Hence all in all we get $2^n-1+c>2^n$ satisfying assignments which implies $f(\varphi)\in\textrm{HALF-SAT}$.

As this problem is also PP-complete the coNP- and NP-hardness directly follow as PP is closed under complement. However the direct reduction from SAT seem to be quite interesting for me.