How hard is it to find a "well-distributed" subset of models of a propositional formula?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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