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

  • $\begingroup$ 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. $\endgroup$ – Austin Buchanan Sep 3 '13 at 17:54
  • $\begingroup$ 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. $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Sebastian Sep 3 '13 at 20:11
  • $\begingroup$ But assuming that my reduction 3. is valid, how can HALF-SAT be NP-complete (PP $\subseteq$ NP) while also being coNP-hard? $\endgroup$ – Sebastian Sep 3 '13 at 20:15
  • 1
    $\begingroup$ The inclusion is in the reverse direction: NP$\subseteq$PP. $\endgroup$ – Yuval Filmus Sep 3 '13 at 20:38
  • $\begingroup$ What does phrase '$P$ closure' mean? $\endgroup$ – T.... Jul 13 '19 at 14:42
  • 1
    $\begingroup$ Problems polytime-reducible to HALF-SAT'. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.