2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ :-( D.W. posted a similar answer while I was writing mine ... $\endgroup$ – Marzio De Biasi Jan 13 '15 at 18:09
  • $\begingroup$ 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. $\endgroup$ – user109711 Jan 18 '15 at 4:49
  • $\begingroup$ 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. $\endgroup$ – user109711 Jan 18 '15 at 4:59
  • $\begingroup$ 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$. $\endgroup$ – user109711 Jan 18 '15 at 5:16
  • $\begingroup$ @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) $\endgroup$ – Marzio De Biasi Jan 18 '15 at 16:27
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.