1
$\begingroup$

I'm trying to prove that $\mathrm{HALF}\text-\mathrm{FALSE}$ is NP-hard, where $\mathrm{HALF}\text-\mathrm{FALSE}$ is the following problem:

given a boolean formula $\phi(x_1,\dots,x_n)$, is there a satisfying assignament in which exactly $n/2$ variables have value false?

Now, i got the problem down if it was like this:

given a boolean formula $\phi(x_1,\dots,x_n)$, is there a satisfying assignament in which at least $n/2$ variables have value false?

the reduction for this modified problem from $\mathrm{SAT}$ to (let's call it $\mathrm{HALF}\text-\mathrm{FALSE}'$) i think is the following: $$f(\phi(x_1,\dots,x_n))=\phi(x_1,\dots,x_n)\bigwedge_{i=1}^{n}y_i'$$

it's correct because $\phi \in SAT \Leftrightarrow f(\phi) \in \mathrm{HALF}\text-\mathrm{FALSE}'$ and $f$ is computable in polynomial time.

Back to the original problem, my thoughts were something like this, if i can transform first the original formula in a formula that is satiasfied only by all true assignament iff the original formula is satisfied, then do the same thing as before. So something like this: $$f(\phi(x_1,\dots,x_n))=\psi(x_1,\dots,x_n)\bigwedge_{i=1}^{n}y_i'$$ where $\psi(x_1,\dots,x_n)$ has only all true assignament iff $\phi(x_1,\dots,x_n)$ is satisfied. But i don't know how to construct $\psi$.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ There is an elementary reduction from SAT to HALF-FALSE. Hint: If $\psi$ is a tautology, then $\varphi \wedge \psi$ is satisfiable if and only if $\varphi$ is satisfiable. Define $\psi$ on fresh copies of all the variables in $\varphi$. $\endgroup$
    – Watercrystal
    Jun 4, 2022 at 21:37
  • $\begingroup$ So you are saying a reduction like $f(\phi(x_1,\dots ,x_n))=\phi(x_1,\dots ,x_n) \wedge \bigvee_{i=1}^{n} (x_i \vee x_i')$ works? i don't see how though, if $\phi$ is satisfiable we don't know how many false variables the assignament has, and i don't understand the logic behind adding a tautology. $\endgroup$
    – giggiox
    Jun 4, 2022 at 21:51
  • $\begingroup$ A tautology $\psi(x'_1, ..., x'_n)$ is satisfied by any assignment to its variables. If $\varphi(x_1, ..., x_n)$ is satisfiable, does $\varphi(x_1, ..., x_n) \wedge \psi(x'_1, ..., x'_n)$ have a satisfying assignment that sets exactly $n$ variables to true? If $\varphi$ is unsatisfiable, does $\varphi \wedge \psi$ have a satisfying assignment (setting exactly $n$ variables to true)? $\endgroup$
    – Watercrystal
    Jun 4, 2022 at 21:58
  • $\begingroup$ Got it! this tricked me because i was thinking that we can't know how many variables are assigned false in the assignament that satisfy the formula, so i was thinking to first force the formula to have all assignament to one, then "mechanically" adding $n$ false assignaments. I think this new way of seeing the problem opened up me many possibilities even for other problems. $\endgroup$
    – giggiox
    Jun 5, 2022 at 6:28

1 Answer 1

Reset to default
1
$\begingroup$

Convert your formula into 3-CNF (not strictly necessary, I think). Duplicate every clause in the formula with new variables and every literal inverted. Then if there exists a satisfying assignment in the original formula one exists in the new one and exactly half of the variables are false. Clearly, if this HALF-FALSE problem is solvable in p-time then so is SAT.

Suppose your 3-CNF formula is $(x_1+x_2'+x_3')(x_1'+x_2+x_3)(x_1'+x_2'+x_3)$. Rewrite it so that it becomes: $$ (x_1+x_2'+x_3')(x_1'+x_2+x_3)(x_1'+x_2'+x_3)\land \\ (y_1'+y_2+y_3)(y_1+y_2'+y_3')(y_1+y_2+y_3') $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ In the process of solving the problem i tried something similar but since i don't know how to prove that this is a correct reduction, i gave up. How can i prove this reduction is correct? I think the idea is that the satisfying assignament to the formula has $k$ false variables, the new formula will have $n-k$ false variables in the same assignament. But how can i prove it? $\endgroup$
    – giggiox
    Jun 5, 2022 at 6:29
  • $\begingroup$ Write a truth table for the new formula. For every row where the output is 1 it must be so that the subformula over the $x$-variables outputs 1 and the subformula over the $y$-variables also outputs 1. Of those, the rows where all $y$-values are negations of the $x$-values must also output 1. If HALF-FALSE can find rows like that in p-time simply read the values of the $x$-variables in that row and you have a satisfying assignment for 3SAT, known to be NP-hard. $\endgroup$
    – Stand with Gaza
    Jun 5, 2022 at 10:51

Your Answer

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

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