<p>Your problem is in fact in $\textsf{DP}$-complete. (For $\textsf{DP}$, see: <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp" rel="nofollow noreferrer">https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp</a>.)</p>

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

<p>$\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.</p>

CC BY-SA 3.0
2017-07-29T15:36:33.020Z
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$
G yehu
CC BY-SA 3.0
2017-07-31T15:08:02.703Z
You're right. There was a slight bug: negations in the clauses of the form (x <-> \neg x') were missing. It should work now.
Ronald de Haan
CC BY-SA 3.0
2017-07-13T10:12:10.863Z
2017-07-31T15:07:14.880Z
2017-07-31T15:07:14.880Z
Ronald de Haan
<p>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:<br>
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)$.<br>
Edit : I suspect that this problem is in dp, but can't prove its completeness. Ideas wil be welcome</p>

<cc.complexity-theory><complexity-classes><polynomial-hierarchy>
Dp completeness of a problem
G yehu
# Dp completeness of a problem

(Asked by: username_0 on 2017-07-13)

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

**Tags:** cc.complexity-theory, complexity-classes, polynomial-hierarchy


---

## 1 answers

### Answer by username_1 on 2017-07-13. Score: 7

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.

> **Comments:**
> **username_0**: 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$  
> **username_1**: You're right. There was a slight bug: negations in the clauses of the form (x <-> \neg x') were missing. It should work now.  

---

