# Dp completeness of a problem

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.
• 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$ Jul 29 '17 at 15:36