<p>$\Sigma_2^{\rm P}$-hardness holds even when $k = 1$. We prove it by considering a reduction from the validity problem for quantified boolean formulas (QBFs) of the form $\exists X \forall Y \alpha$ where $X = \{x_1, \dots, x_n\}$ and $Y = \{y_1, \dots, y_m\}$ are two disjoint sets of propositional atoms and $Var(\alpha) = X \cup Y$. Consider such a QBF. Let us define new sets of fresh variables $Z = \{z_1, \dots, z_{m+1}\}$ and for every $i \in \{1, \dots, m\}$, $X^i = \{x_1^i, \dots, x_n^i\}$. Let us associate with the QBF the propositional formula $\phi$ defined over $\bigcup_{i = 1}^m{X^i} \cup X \cup Y \cup Z$ as:</p>

<p>$\phi = \bigwedge_{i=1}^n\bigwedge_{j=1}^m{x_i \leftrightarrow x_i^j} \wedge (\neg \alpha \rightarrow \bigwedge_{i = 1}^{m+1}{z_i})$.</p>

<p>Note that $|Var(\phi)| = n(m+1) + 2m + 1$.</p>

<p>We prove that the QBF $\exists X \forall Y \alpha$ is valid if and only if there exists an interpretation $\omega \in Mod(\phi)$ such that $\forall \eta \in Mod(\phi)$, $d_H(\omega, \eta) \leq n(m + 1) + m$.</p>

<p>($\Rightarrow$ part) Assume that $\exists X \forall Y \alpha$ is valid. Then there exists an assignment over $X$ such that any completion of it over $X \cup Y$ satisfies $\neg \alpha$. Let $\omega'$ be such an assignment over $X$. We must have $\omega'(z_1) = \dots = \omega'(z_{m+1}) = 1$.
Then consider an assignement $\omega$ over $Var(\phi)$ satisfying the following conditions:</p>

<p>$\forall i \in \{1, \dots, n\}$, $\omega(x_i) = \omega(x^1_i) = \dots = \omega(x^m_i) = |1 - \omega'(x_i)|$,
and for all other variables $s \in Y \cup Z$, $\omega(s) = 1$.</p>

<p>Let $\eta \in Mod(\phi)$. Then we fall in exactly two cases:
(i) $\eta$ differs from $\omega$ on all variables from $X$. In this case, $\eta$ and $\omega'$ have the same value on all variables from $\bigcup_{i=1}^m{X^i} \cup X$, so $\eta$ shares the same property as $\omega'$ on the fact that $\eta \models \neg \alpha$. Thus $\eta$ and $\omega$ have the same value on all variables from $Z$, i.e., $\forall i \in \{1, \dots, m+1\}$, $\eta(z_i) = \omega(z_i) = 1$, so $\eta$ and $\omega$ share the same value on at least $m + 1$ variables. Hence, $d_H(\eta, \omega) \leq n(m + 1) + m$.
(ii) $\eta$ and $\omega$ have the same value on some variable $x_a$ from $X$. Then they also have the same value on all variables $x^i_a$ from $X^i$, i.e., $\forall i \in \{1, \dots, m\}$, $\eta(x^i_a) = \omega(x^i_a)$, so $\eta$ and $\omega$ share the same value on at least $m + 1$ variables. Hence, $d_H(\eta, \omega) \leq |Var(\phi)| - (m + 1) = n(m + 1) + m$.</p>

<p>We just proved that $\forall \eta \in Mod(\phi)$, $d_H(\omega, \eta) \leq n(m + 1) + m$. That is, we proved that if QBF $\exists X \forall Y \alpha$ is valid, then there exists an interpretation $\omega \in Mod(\phi)$ such that $\forall \eta \in Mod(\phi)$, $d_H(\omega, \eta) \leq n(m + 1) + m$.</p>

<p>($\Leftarrow$ part) Assume that $\exists X \forall Y \alpha$ is not valid. So it holds that for any assignment over $X$ there is a completion of it over $X \cup Y$ satisfying $\neg \phi$. Let $\omega \in Mod(\phi)$. Consider the assignment $\eta$ over $\bigcup_{i = 1}^m{X^i} \cup X \cup Z$ satisfying the following conditions:</p>

<p>$\forall i \in \{1, \dots, n\}$, $\eta(x_i) = \eta(x^1_i) = \dots = \eta(x^m_i) = |1 - \omega(x_i)|$,
and $\forall i \in \{1, \dots, m+1\}$, $\eta(z_i) = |1 - \omega(z_i)|$.
By hypothesis, $\eta$ can completed to an assignment over $Var(\phi)$ such that $\eta \models \neg \phi$, and $\eta$ satisfies all constraints of $\phi$, thus $\eta \in Mod(\phi)$. Moreover, $\eta$ differs from $\omega$ on $n(m+1) + m + 1$ variables. So for every $\omega \in Mod(\phi)$, we can find an assignement $\eta \in Mod(\phi)$ such that $d_H(\eta, \omega) &gt; n(m+1) + m$. Hence, there exists no interpretation $\omega \in Mod(\phi)$ such that $\forall \eta \in Mod(\phi)$, $d_H(\omega, \eta) \leq n(m + 1) + m$.</p>

<p>This shows that the QBF $\exists X \forall Y \alpha$ is valid if and only if there exists an interpretation $\omega \in Mod(\phi)$ such that $\forall \eta \in Mod(\phi)$, $d_H(\omega, \eta) \leq n(m + 1) + m$, which concludes the proof that the initial problem is $\Sigma_2^{\rm P}$-hard. Since we already knew that it is in $\Sigma_2^{\rm P}$, it is $\Sigma_2^{\rm P}$-complete.</p>

CC BY-SA 3.0
2015-01-20T20:52:10.850Z
2015-01-20T20:52:10.850Z
user109711
<p>The first part of the question leads to a coNP-hard problem; this is a reduction from UNSAT.</p>

<p>Suppose that $\phi$ is a SAT formula with $n$ variables. Check if it is satisfied by $(1,1,...,1),(0,1,...1),(1,0,...,1),...(1,1,...,0)$ if yes, build a dum false instance of your problem. Otherwise build:</p>

<p>$$\phi' =( \phi ) \lor (x_1 \land ... \land x_n)$$</p>

<p>Which is satisfiable and $w_1 = (1,...,1) \in Mod(\phi')$. Note that for all $w \neq w_1$ we have $w \in Mod(\phi') \Leftrightarrow w \in Mod(\phi)$  , if you pick $k = 1$, and $\alpha= 1$; then $\mathcal{I}$ must contain only one element and must be at Hamming distance one from the other elements of the model.</p>

<p>But by construction the only $n$ models at Hamming distance 1 from $w_1$ $(0,1,...,1),(1,0,...,1)$ are not in $Mod(\phi) $and are not in $Mod(\phi')$; so your problem has a solution if and only if $\mathcal{I} = \{ w_1 \} = Mod(\phi' )$; if and only if the original $\phi$ is unsatisfiable.</p>

CC BY-SA 3.0
2015-01-13T18:09:11.890Z
:-( D.W. posted a similar answer while I was writing mine ...
Marzio De Biasi
CC BY-SA 3.0
2015-01-18T04:49:10.237Z
I think the HRC problem is different, because the $p$ strings to find are not in the given set $S$. In particular, 1-HRC is NP-hard, while it is obviously in P in my case.
user109711
CC BY-SA 3.0
2015-01-18T04:59:22.493Z
If the whole set $Mod(\phi)$ is given in input, then the problem is NP-hard in the case where any distance $d$ between interpretations can be considered. We reduce the set cover problem to ours. Given a graph $G = (V, A)$, associate with each vertex from V some unique interpretation. Define for every $(a, b) \in A$ the distance $d(a, b)$ as the length of the shortest path between $a$ and $b$ in $G$. Then there exists a set cover of size $\leq \alpha$ in $G$ if and only if the translated instance is a yes one, with $\alpha = 1$.
But I cannot prove NP-hardness when using the Hamming distance.
user109711
CC BY-SA 3.0
2015-01-18T05:16:44.630Z
In my previous comment, I mean "vertex cover problem", not "set cover problem". And the first occurrence of $\alpha$ should be replaced by a $k$.
user109711
CC BY-SA 3.0
2015-01-18T16:27:22.770Z
@user109711: I saw that you posted a solution for the explicit case, but perhaps you can construct $Mod(\phi)$ implicitly using a DNF (of polynomial size w.r.t. $|Mod(\phi)|$) in which every clause is exactly $(l_1 \land ... \land l_n), l_i \in \{x_i, \neg x_i\}$ (negated or unnegated); see the part of my answer in which I build the elements of S (that part is correct). Don't forget that the implicit case is also coNP-hard (see the first part of my answer and DW's answer)
Marzio De Biasi
CC BY-SA 3.0
2015-01-18T16:53:55.643Z
I am afraid I do not understand your point here. In the succinct case, since any formula $\phi$ can be considered in input, constructing the set $Mod(\phi)$ or using a DNF cannot be done in polynomial time in the general case (otherwise, the succinct form of the problem would also be in $\mathsf{NP}$, as it is the case for the "explicit" case). I acknowledge the $\mathsf{coNP}$-hardness of the succinct version of the problem (I am now editing the question to include this result), but I believe the problem is "harder" than $\mathsf{coNP}$, i.e., maybe $\Sigma_2^{\rm P}$-hard.
user109711
CC BY-SA 3.0
2015-01-18T17:17:41.763Z
@user109711: probably I'm missing something (so take my commentns with caution), but it seems that in your reduction from vertex cover to the explicit version of your problem, you BUILD an explicit $Mod(\varphi)$ that has only a polynomial number of members. So you can also build a DNF formula that has exactly $Mod(\varphi)$ as model, and end up with a reduction from vertex cover to the "implicit" version of your problem (i.e. prove that it is NP-hard).
Marzio De Biasi
CC BY-SA 3.0
2015-01-18T17:39:41.123Z
I understand and agree, the "implicit" version of the problem is $\mathsf{NP}$-hard by doing this way.
user109711
CC BY-SA 3.0
2015-01-18T17:40:04.840Z
We also know now that it is $\mathsf{coNP}$-hard and belongs to $\Sigma_2^{\rm P}$. The thing is now to show the exact complexity of the problem, and I believe it is $\Sigma_2^{\rm P}$-hard, thus $\Sigma_2^{\rm P}$-complete.
I just found a paper from T. Tantau "Complexity of the Undirected Radius and Diameter Problems for Succinctly Represented Graphs" in which a seemingly similar problem, the "succinct-undirected-1-radius" problem, is proved to be $\Sigma_2^{\rm P}$-complete. I will given an update if I find a convenient reduction from this problem.
user109711
CC BY-SA 3.0
2015-01-13T18:08:43.880Z
2015-01-18T17:13:02.697Z
2015-01-18T17:13:02.697Z
Marzio De Biasi
<p>Well, I don't know what the exact complexity class is, but the problem is hard: a polynomial-time algorithm for this problem would imply P=NP.  Just take $k=0$; then the answer to your problem is yes if and only if $\phi$ is unsatisfiable.  Therefore, any polynomial-time algorithm for your problem would imply P=NP.</p>

<hr>

<p>If you don't like relying on the special case $k=0$, here's a related construction.  Let $\psi$ be a boolean formula on $n$ variables $x_1,\dots,x_n$.  Introduce $n+1$ new variables $y_0,\dots,y_n$.  Define the formula</p>

<p>$$\phi := (\psi \land y_0 \land \dots \land y_n) \lor (\neg y_0 \land \dots \neg y_n).$$</p>

<p>Set $k=1$ and $\alpha=n$.  If $\psi$ is satisfiable, the answer to your problem is no.  If $\psi$ is not satisfiable, the answer to your problem is yes.</p>

CC BY-SA 3.0
2015-01-13T18:04:19.123Z
2015-01-13T18:04:19.123Z
D.W.
<p>We consider the propositional language $\mathcal{L}_{\mathit{PS}}$ defined over a finite alphabet $\mathit{PS}$ and the usual logical connectives. An interpretation is an assignment $\mathit{PS} \mapsto \{true, false\}$, and a model of a formula $\phi \in \mathcal{L}_{\mathit{PS}}$ is an interpretation $\omega$ which makes $\phi$ true in the usual way. The set of models of a formula $\phi$ is denoted $Mod(\phi)$. The Hamming distance $d_H(\omega, \omega')$ between two interpretations is the number differences between them, i.e., $d_H(\omega, \omega') = |\{x \in \mathit{PS} \mid \omega(x) \neq \omega'(x)\}|$.</p>

<p>I am interested in the computational complexity of the following decision problem. Given a formula $\phi$, an integer $k$ given in unary and a number $\alpha$, does there exist a set $\mathcal{I} \subseteq Mod(\phi)$ such that $|\mathcal{I}| \leq k$ and such that $\forall \omega' \in Mod(\phi)$, $\exists \omega \in \mathcal{I}$, $d_H(\omega, \omega') \leq \alpha$? Intuitively, this problem asks whether there is a subset (of size at most $k$) of models of a given formula such that every model of the formula is "close" enough (wrt the distance threshold $\alpha$) to some model of the subset.</p>

<p>Actually, I am also wondering about the hardness of the above problem when the set $Mod(\phi)$ is given explicitly in input (at least, this one is in $\mathbf{NP}$, but is it $\mathbf{NP}$-hard?)</p>

<p><strong>Update:</strong></p>

<p>The following is the answer for the case where the set $Mod(\phi)$ is explicitely given in input.
The problem is $\mathsf{NP}$-hard by reduction from the vertex cover problem on cubic graph, which is known to be $\mathsf{NP}$-hard.
Let $G = (V, A)$ be a cubic graph with $V = \{v_1, \dots, v_n\}$ and $A = \{a_1, \dots, a_m\}$ and $k$ be a positive integer.
We associate with every edge $a_j \in A$ a propositional variable $f(a_j) = x_j$ and denote $\{x_1, \dots, x_m\} = \mathit{PS}$.
We associate with every vertex $v_i \in V$ an interpretation $g(v_i) = \omega_i$ defined for every $j \in \{1, \dots, m\}$ as $\omega_i(x_j) = 1$ if the edge $a_j \in A$ is incident to the vertex $v_i$, $0$ otherwise. Denote $\{\omega_1, \dots, \omega_n\} = \mathcal{S}$ ($\mathcal{S}$ stands for the set of models $Mod(\phi)$ of some formula $\phi$, but which is here defined explicitely). One can see that for every $\omega_i, \omega_j \in \mathcal{S}$, $d_H(\omega_i, \omega_j) = 4$ if $v_i$ and $v_j$ are adjacent in $G$, otherwise $d_H(\omega_i, \omega_j) = 6$. Therefore, $G$ admits a vertex cover $V'$ such that $|V'| \leq k$ if and only if the set $\mathcal{I} = \{g(v_i) \mid v_i \in V'\}$ satisfies $\forall \omega_j \in \mathcal{S}$, $\exists \omega_i \in \mathcal{I}$, $d_H(\omega_i, \omega_j) \leq 4$.</p>

<p>For the succinct case (i.e., where considering a formula $\phi$ instead of a list of interpretations), then the problem is still open. From the answers of Marzio De Biasi and D.W., it is $\mathsf{coNP}$-hard. Moreover, it is in $\mathsf{NP}^\mathsf{NP} = \Sigma_2^{\rm P}$. Indeed, one can use the following non-deterministic algorithm with $\mathsf{NP}$ oracle: (i) guess a set $\mathcal{I}$ of interpretations such that $|\mathcal{I}| \leq k$; (ii) check in polynomial time that $\forall \omega \in \mathcal{I}$, $\omega \in Mod(\phi)$, and check using one call to the $\mathsf{NP}$-oracle that $\forall \omega' \in Mod(\phi)$, $\exists \omega \in \mathcal{I}$, $d_H(\omega, \omega') \leq \alpha$.</p>

<p>I still need to characterize the exact complexity of the problem. Intuitively, it seems that the problem is $\Sigma_2^{\rm P}$-hard (thus, it would be $\Sigma_2^{\rm P}$-complete in this case). Does anybody know an extension of the vertex cover problem to some $\Sigma_2^{\rm P}$-hard problem? Otherwise, a reduction from the validity problem of a QBF of the form $\exists X \forall Y \psi$ to our problem seems cumbersome.</p>

<np-hardness><complexity-classes><boolean-formulas>
How hard is it to find a "well-distributed" subset of models of a propositional formula?
user109711
# How hard is it to find a "well-distributed" subset of models of a propositional formula?

(Asked by: username_0 on 2015-01-13)

We consider the propositional language $\mathcal{L}\_{\mathit{PS}}$ defined over a finite alphabet $\mathit{PS}$ and the usual logical connectives. An interpretation is an assignment $\mathit{PS} \mapsto \{true, false\}$, and a model of a formula $\phi \in \mathcal{L}\_{\mathit{PS}}$ is an interpretation $\omega$ which makes $\phi$ true in the usual way. The set of models of a formula $\phi$ is denoted $Mod(\phi)$. The Hamming distance $d\_H(\omega, \omega')$ between two interpretations is the number differences between them, i.e., $d\_H(\omega, \omega') = |\{x \in \mathit{PS} \mid \omega(x) \neq \omega'(x)\}|$.

I am interested in the computational complexity of the following decision problem. Given a formula $\phi$, an integer $k$ given in unary and a number $\alpha$, does there exist a set $\mathcal{I} \subseteq Mod(\phi)$ such that $|\mathcal{I}| \leq k$ and such that $\forall \omega' \in Mod(\phi)$, $\exists \omega \in \mathcal{I}$, $d\_H(\omega, \omega') \leq \alpha$? Intuitively, this problem asks whether there is a subset (of size at most $k$) of models of a given formula such that every model of the formula is "close" enough (wrt the distance threshold $\alpha$) to some model of the subset.

Actually, I am also wondering about the hardness of the above problem when the set $Mod(\phi)$ is given explicitly in input (at least, this one is in $\mathbf{NP}$, but is it $\mathbf{NP}$-hard?)

**Update:**

The following is the answer for the case where the set $Mod(\phi)$ is explicitely given in input.
The problem is $\mathsf{NP}$-hard by reduction from the vertex cover problem on cubic graph, which is known to be $\mathsf{NP}$-hard.
Let $G = (V, A)$ be a cubic graph with $V = \{v\_1, \dots, v\_n\}$ and $A = \{a\_1, \dots, a\_m\}$ and $k$ be a positive integer.
We associate with every edge $a\_j \in A$ a propositional variable $f(a\_j) = x\_j$ and denote $\{x\_1, \dots, x\_m\} = \mathit{PS}$.
We associate with every vertex $v\_i \in V$ an interpretation $g(v\_i) = \omega\_i$ defined for every $j \in \{1, \dots, m\}$ as $\omega\_i(x\_j) = 1$ if the edge $a\_j \in A$ is incident to the vertex $v\_i$, $0$ otherwise. Denote $\{\omega\_1, \dots, \omega\_n\} = \mathcal{S}$ ($\mathcal{S}$ stands for the set of models $Mod(\phi)$ of some formula $\phi$, but which is here defined explicitely). One can see that for every $\omega\_i, \omega\_j \in \mathcal{S}$, $d\_H(\omega\_i, \omega\_j) = 4$ if $v\_i$ and $v\_j$ are adjacent in $G$, otherwise $d\_H(\omega\_i, \omega\_j) = 6$. Therefore, $G$ admits a vertex cover $V'$ such that $|V'| \leq k$ if and only if the set $\mathcal{I} = \{g(v\_i) \mid v\_i \in V'\}$ satisfies $\forall \omega\_j \in \mathcal{S}$, $\exists \omega\_i \in \mathcal{I}$, $d\_H(\omega\_i, \omega\_j) \leq 4$.

For the succinct case (i.e., where considering a formula $\phi$ instead of a list of interpretations), then the problem is still open. From the answers of username_1 and username_2, it is $\mathsf{coNP}$-hard. Moreover, it is in $\mathsf{NP}^\mathsf{NP} = \Sigma\_2^{\rm P}$. Indeed, one can use the following non-deterministic algorithm with $\mathsf{NP}$ oracle: (i) guess a set $\mathcal{I}$ of interpretations such that $|\mathcal{I}| \leq k$; (ii) check in polynomial time that $\forall \omega \in \mathcal{I}$, $\omega \in Mod(\phi)$, and check using one call to the $\mathsf{NP}$-oracle that $\forall \omega' \in Mod(\phi)$, $\exists \omega \in \mathcal{I}$, $d\_H(\omega, \omega') \leq \alpha$.

I still need to characterize the exact complexity of the problem. Intuitively, it seems that the problem is $\Sigma\_2^{\rm P}$-hard (thus, it would be $\Sigma\_2^{\rm P}$-complete in this case). Does anybody know an extension of the vertex cover problem to some $\Sigma\_2^{\rm P}$-hard problem? Otherwise, a reduction from the validity problem of a QBF of the form $\exists X \forall Y \psi$ to our problem seems cumbersome.

**Tags:** np-hardness, complexity-classes, boolean-formulas


---

## 3 answers

### Answer by username_0 on 2015-01-20. Score: 0 | Accepted answer

$\Sigma\_2^{\rm P}$-hardness holds even when $k = 1$. We prove it by considering a reduction from the validity problem for quantified boolean formulas (QBFs) of the form $\exists X \forall Y \alpha$ where $X = \{x\_1, \dots, x\_n\}$ and $Y = \{y\_1, \dots, y\_m\}$ are two disjoint sets of propositional atoms and $Var(\alpha) = X \cup Y$. Consider such a QBF. Let us define new sets of fresh variables $Z = \{z\_1, \dots, z\_{m+1}\}$ and for every $i \in \{1, \dots, m\}$, $X^i = \{x\_1^i, \dots, x\_n^i\}$. Let us associate with the QBF the propositional formula $\phi$ defined over $\bigcup\_{i = 1}^m{X^i} \cup X \cup Y \cup Z$ as:

$\phi = \bigwedge\_{i=1}^n\bigwedge\_{j=1}^m{x\_i \leftrightarrow x\_i^j} \wedge (\neg \alpha \rightarrow \bigwedge\_{i = 1}^{m+1}{z\_i})$.

Note that $|Var(\phi)| = n(m+1) + 2m + 1$.

We prove that the QBF $\exists X \forall Y \alpha$ is valid if and only if there exists an interpretation $\omega \in Mod(\phi)$ such that $\forall \eta \in Mod(\phi)$, $d\_H(\omega, \eta) \leq n(m + 1) + m$.

($\Rightarrow$ part) Assume that $\exists X \forall Y \alpha$ is valid. Then there exists an assignment over $X$ such that any completion of it over $X \cup Y$ satisfies $\neg \alpha$. Let $\omega'$ be such an assignment over $X$. We must have $\omega'(z\_1) = \dots = \omega'(z\_{m+1}) = 1$.
Then consider an assignement $\omega$ over $Var(\phi)$ satisfying the following conditions:

$\forall i \in \{1, \dots, n\}$, $\omega(x\_i) = \omega(x^1\_i) = \dots = \omega(x^m\_i) = |1 - \omega'(x\_i)|$,
and for all other variables $s \in Y \cup Z$, $\omega(s) = 1$.

Let $\eta \in Mod(\phi)$. Then we fall in exactly two cases:
(i) $\eta$ differs from $\omega$ on all variables from $X$. In this case, $\eta$ and $\omega'$ have the same value on all variables from $\bigcup\_{i=1}^m{X^i} \cup X$, so $\eta$ shares the same property as $\omega'$ on the fact that $\eta \models \neg \alpha$. Thus $\eta$ and $\omega$ have the same value on all variables from $Z$, i.e., $\forall i \in \{1, \dots, m+1\}$, $\eta(z\_i) = \omega(z\_i) = 1$, so $\eta$ and $\omega$ share the same value on at least $m + 1$ variables. Hence, $d\_H(\eta, \omega) \leq n(m + 1) + m$.
(ii) $\eta$ and $\omega$ have the same value on some variable $x\_a$ from $X$. Then they also have the same value on all variables $x^i\_a$ from $X^i$, i.e., $\forall i \in \{1, \dots, m\}$, $\eta(x^i\_a) = \omega(x^i\_a)$, so $\eta$ and $\omega$ share the same value on at least $m + 1$ variables. Hence, $d\_H(\eta, \omega) \leq |Var(\phi)| - (m + 1) = n(m + 1) + m$.

We just proved that $\forall \eta \in Mod(\phi)$, $d\_H(\omega, \eta) \leq n(m + 1) + m$. That is, we proved that if QBF $\exists X \forall Y \alpha$ is valid, then there exists an interpretation $\omega \in Mod(\phi)$ such that $\forall \eta \in Mod(\phi)$, $d\_H(\omega, \eta) \leq n(m + 1) + m$.

($\Leftarrow$ part) Assume that $\exists X \forall Y \alpha$ is not valid. So it holds that for any assignment over $X$ there is a completion of it over $X \cup Y$ satisfying $\neg \phi$. Let $\omega \in Mod(\phi)$. Consider the assignment $\eta$ over $\bigcup\_{i = 1}^m{X^i} \cup X \cup Z$ satisfying the following conditions:

$\forall i \in \{1, \dots, n\}$, $\eta(x\_i) = \eta(x^1\_i) = \dots = \eta(x^m\_i) = |1 - \omega(x\_i)|$,
and $\forall i \in \{1, \dots, m+1\}$, $\eta(z\_i) = |1 - \omega(z\_i)|$.
By hypothesis, $\eta$ can completed to an assignment over $Var(\phi)$ such that $\eta \models \neg \phi$, and $\eta$ satisfies all constraints of $\phi$, thus $\eta \in Mod(\phi)$. Moreover, $\eta$ differs from $\omega$ on $n(m+1) + m + 1$ variables. So for every $\omega \in Mod(\phi)$, we can find an assignement $\eta \in Mod(\phi)$ such that $d\_H(\eta, \omega) > n(m+1) + m$. Hence, there exists no interpretation $\omega \in Mod(\phi)$ such that $\forall \eta \in Mod(\phi)$, $d\_H(\omega, \eta) \leq n(m + 1) + m$.

This shows that the QBF $\exists X \forall Y \alpha$ is valid if and only if there exists an interpretation $\omega \in Mod(\phi)$ such that $\forall \eta \in Mod(\phi)$, $d\_H(\omega, \eta) \leq n(m + 1) + m$, which concludes the proof that the initial problem is $\Sigma\_2^{\rm P}$-hard. Since we already knew that it is in $\Sigma\_2^{\rm P}$, it is $\Sigma\_2^{\rm P}$-complete.


---

### Answer by username_1 on 2015-01-13. Score: 3

The first part of the question leads to a coNP-hard problem; this is a reduction from UNSAT.

Suppose that $\phi$ is a SAT formula with $n$ variables. Check if it is satisfied by $(1,1,...,1),(0,1,...1),(1,0,...,1),...(1,1,...,0)$ if yes, build a dum false instance of your problem. Otherwise build:

$$\phi' =( \phi ) \lor (x\_1 \land ... \land x\_n)$$

Which is satisfiable and $w\_1 = (1,...,1) \in Mod(\phi')$. Note that for all $w \neq w\_1$ we have $w \in Mod(\phi') \Leftrightarrow w \in Mod(\phi)$ , if you pick $k = 1$, and $\alpha= 1$; then $\mathcal{I}$ must contain only one element and must be at Hamming distance one from the other elements of the model.

But by construction the only $n$ models at Hamming distance 1 from $w\_1$ $(0,1,...,1),(1,0,...,1)$ are not in $Mod(\phi) $and are not in $Mod(\phi')$; so your problem has a solution if and only if $\mathcal{I} = \{ w\_1 \} = Mod(\phi' )$; if and only if the original $\phi$ is unsatisfiable.

> **Comments:**
> **username_1**: :-( username_2 posted a similar answer while I was writing mine ...  
> **username_0**: I think the HRC problem is different, because the $p$ strings to find are not in the given set $S$. In particular, 1-HRC is NP-hard, while it is obviously in P in my case.  
> **username_0**: If the whole set $Mod(\phi)$ is given in input, then the problem is NP-hard in the case where any distance $d$ between interpretations can be considered. We reduce the set cover problem to ours. Given a graph $G = (V, A)$, associate with each vertex from V some unique interpretation. Define for every $(a, b) \in A$ the distance $d(a, b)$ as the length of the shortest path between $a$ and $b$ in $G$. Then there exists a set cover of size $\leq \alpha$ in $G$ if and only if the translated instance is a yes one, with $\alpha = 1$. But I cannot prove NP-hardness when using the Hamming distance.  
> **username_0**: In my previous comment, I mean "vertex cover problem", not "set cover problem". And the first occurrence of $\alpha$ should be replaced by a $k$.  
> **username_1**: @username_0: I saw that you posted a solution for the explicit case, but perhaps you can construct $Mod(\phi)$ implicitly using a DNF (of polynomial size w.r.t. $|Mod(\phi)|$) in which every clause is exactly $(l_1 \land ... \land l_n), l_i \in \{x_i, \neg x_i\}$ (negated or unnegated); see the part of my answer in which I build the elements of S (that part is correct). Don't forget that the implicit case is also coNP-hard (see the first part of my answer and DW's answer)  
> **username_0**: I am afraid I do not understand your point here. In the succinct case, since any formula $\phi$ can be considered in input, constructing the set $Mod(\phi)$ or using a DNF cannot be done in polynomial time in the general case (otherwise, the succinct form of the problem would also be in $\mathsf{NP}$, as it is the case for the "explicit" case). I acknowledge the $\mathsf{coNP}$-hardness of the succinct version of the problem (I am now editing the question to include this result), but I believe the problem is "harder" than $\mathsf{coNP}$, i.e., maybe $\Sigma_2^{\rm P}$-hard.  
> **username_1**: @username_0: probably I'm missing something (so take my commentns with caution), but it seems that in your reduction from vertex cover to the explicit version of your problem, you BUILD an explicit $Mod(\varphi)$ that has only a polynomial number of members. So you can also build a DNF formula that has exactly $Mod(\varphi)$ as model, and end up with a reduction from vertex cover to the "implicit" version of your problem (i.e. prove that it is NP-hard).  
> **username_0**: I understand and agree, the "implicit" version of the problem is $\mathsf{NP}$-hard by doing this way.  
> **username_0**: We also know now that it is $\mathsf{coNP}$-hard and belongs to $\Sigma_2^{\rm P}$. The thing is now to show the exact complexity of the problem, and I believe it is $\Sigma_2^{\rm P}$-hard, thus $\Sigma_2^{\rm P}$-complete. I just found a paper from T. Tantau "Complexity of the Undirected Radius and Diameter Problems for Succinctly Represented Graphs" in which a seemingly similar problem, the "succinct-undirected-1-radius" problem, is proved to be $\Sigma_2^{\rm P}$-complete. I will given an update if I find a convenient reduction from this problem.  

---

### Answer by username_2 on 2015-01-13. Score: 3

Well, I don't know what the exact complexity class is, but the problem is hard: a polynomial-time algorithm for this problem would imply P=NP. Just take $k=0$; then the answer to your problem is yes if and only if $\phi$ is unsatisfiable. Therefore, any polynomial-time algorithm for your problem would imply P=NP.

---

If you don't like relying on the special case $k=0$, here's a related construction. Let $\psi$ be a boolean formula on $n$ variables $x\_1,\dots,x\_n$. Introduce $n+1$ new variables $y\_0,\dots,y\_n$. Define the formula

$$\phi := (\psi \land y\_0 \land \dots \land y\_n) \lor (\neg y\_0 \land \dots \neg y\_n).$$

Set $k=1$ and $\alpha=n$. If $\psi$ is satisfiable, the answer to your problem is no. If $\psi$ is not satisfiable, the answer to your problem is yes.


---

