Given a Boolean formula $\varphi$ over the variables $\{x_1...x_n\}$ , an assignment $T_0$ for $\varphi$ and an integer $k$, I am interested in the following question:
Does $k$ is the minimal number of bits that we have to change with respect to $T_0$ to change the value of $\varphi$? I.e. there exists an assignment $T_1$ such that $T_1$ is different from $T_0$ in at least $k+1$ different places and $T_0(\varphi) \neq T_1(\varphi)$, and for all $T$ such that $T$ is different from $T_0$ in $k$ places or less, it holds that $T(\varphi)=T_0(\varphi)$.
Edit : I suspect that this problem is in dp, but can't prove its completeness. Ideas wil be welcome


Your problem is in fact in $\textsf{DP}$-complete. (For $\textsf{DP}$, see: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp.)

You can show membership in $\textsf{DP}$ by reducing your problem to the $\textsf{DP}$-complete problem SAT-UNSAT, which consists of all pairs $(\varphi_1,\varphi_2)$ of propositional formulas such that $\varphi_1$ is satisfiable and $\varphi_2$ is unsatisfiable. Given an instance $(\varphi,T_0,k)$ of your problem, we construct an instance $(\varphi_1,\varphi_2)$ of SAT-UNSAT. The problem of deciding whether there is some $T_1$ such that $T_1$ differs from $T_0$ in at least $k$ places and $T_0(\varphi) \neq T_1(\varphi)$ is in $\textsf{NP}$, so (by $\textsf{NP}$-completeness of SAT) we can construct some $\varphi_1$ in poly-time that is satisfiable if and only if an appropriate $T_1$ exists. Similarly, the problem of deciding whether for all $T_2$ that differ from $T_0$ in at most $k-1$ places it holds that $T_2(\varphi) = T_0(\varphi)$ is in $\textsf{coNP}$, so (by $\textsf{coNP}$-completeness of UNSAT) we can construct some $\varphi_2$ in poly-time that is unsatisfiable if and only if this property holds for all suitable $T_2$.

$\textsf{DP}$-hardness can be shown by a reduction from SAT-UNSAT, that I will sketch here. Let $(\varphi_1,\varphi_2)$ be an instance of SAT-UNSAT. Without loss of generality, assume that $\varphi_1$ contains exactly one variable more than $\varphi_2$. Let $x_1,\dotsc,x_{n+1}$ be the variables occurring in $\varphi_1$, and let $y_1,\dotsc,y_{n}$ be the variables occurring in $\varphi_2$. Then let the formula $\varphi'_1$ be $\varphi_1 \wedge \bigwedge_{i=1}^{n+1} (x_i \leftrightarrow \neg x'_i)$, where $x'_1,\dotsc,x'_n$ are fresh variables. Similarly, let the formula $\varphi'_2$ be $\varphi_2 \wedge \bigwedge_{i=1}^{n} (y_i \leftrightarrow \neg y'_i)$, where $x'_1,\dotsc,x'_n$ are fresh variables. We then define the formula $\varphi$ as $\varphi'_1 \vee \varphi'_2$. We let $T_0$ be the truth assignment that sets all variables to false. Finally, we let $k = n+1$. We know that $T_0(\varphi) = 0$. Satisfying $\varphi$ by flipping $k-1$ bits in $T_0$ can be done iff $\varphi_2$ is satisfiable, and satisfying $\varphi$ by flipping $k$ bits can be done iff $\varphi_1$ is satisfiable. Together, $k$ is the minimal number of bits to flip to satisfy $\varphi$ if and only if $(\varphi_1,\varphi_2) \in$ SAT-UNSAT.

  • $\begingroup$ Looking at it again, why the initial assignment gives 0 to $\varphi$? It gives 1 to all the clauses of the form x iff x', and you don't know what it gives to $\varphi1$ $\endgroup$
    – G yehu
    Jul 29 '17 at 15:36
  • $\begingroup$ You're right. There was a slight bug: negations in the clauses of the form (x <-> \neg x') were missing. It should work now. $\endgroup$ Jul 31 '17 at 15:08

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.