How hard is it to find a "well-distributed" subset of models of a propositional formula? 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 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$.

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