1
$\begingroup$

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

$\endgroup$
2
  • $\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$ Sep 3, 2013 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, 2013 at 18:13

2 Answers 2

8
$\begingroup$

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

$\endgroup$
5
  • $\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, 2013 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, 2013 at 20:15
  • 1
    $\begingroup$ The inclusion is in the reverse direction: NP$\subseteq$PP. $\endgroup$ Sep 3, 2013 at 20:38
  • $\begingroup$ What does phrase '$P$ closure' mean? $\endgroup$
    – Turbo
    Jul 13, 2019 at 14:42
  • 1
    $\begingroup$ Problems polytime-reducible to HALF-SAT'. $\endgroup$ Jul 13, 2019 at 15:03
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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