# Determining whether formula is only satisfied by the all-true assignment

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

• 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$. Commented Jun 4, 2022 at 21:37
• 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. Commented Jun 4, 2022 at 21:51
• 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)? Commented Jun 4, 2022 at 21:58
• 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. Commented Jun 5, 2022 at 6:28

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')$$
• 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? Commented Jun 5, 2022 at 6:29
• 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. Commented Jun 5, 2022 at 10:51