<figure><img src="image_1.png" /></figure>

HAL
open science

# A note on the inapproximability of the Minimum Monotone Satisfying Assignment problem

Dimitri Watel, Marc-Antoine Weisser

► To cite this version:

Dimitri Watel, Marc-Antoine Weisser. A note on the inapproximability of the Minimum Monotone Satisfying Assignment problem. 2016. hal-01377704

HAL Id: hal-01377704

https://hal.science/hal-01377704

Preprint submitted on 7 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A note on the inapproximability of the Minimum
Monotone Satisfying Assignment problem

Dimitri Watel$^{a,b,*}$, Marc-Antoine Weisser$^{c,d}$

$^{a}$ENSIHE, 1 rue de la Résistance, 91000, Évry, France

$^b$CEDRIC-CNAM 292 Rue Saint-Martin, 75003, Paris, France

$^c$CentraleSupélec, 3 rue Joliot-Curie, 91192 Gif sur Yvette, France

$^d$LRI, Bât 650, Rue Noetzlin, 91192 Gif sur Yvette, France

**Abstract**

The Minimum Monotone Satisfying Assignment problem (MMSA) consists,
given a monotone boolean formula $\varphi$, in searching for a minimum number of
true variables such that $\varphi$ is satisfied. A polynomial inapproximability ratio
was given by Dinur et al. However, this ratio depends on a parameter that is
not the size of the MMSA instance. It is instead the size of the problem from
which the reduction is done. Consequently, it is hard to reuse this result to
prove other hardness of approximability. In this paper, we deepen the previous
work and prove two inapproximability ratio for MMSA depending on the size
of the formula and the number of variables and we prove that MMSA cannot
be polylogarithmically approximated.

Keywords: Combinatorial optimization, Polynomial approximation, Minimum Monotone Satisfying Assignment problem

**1. Introduction**

**Problem 1. Minimum Monotone Satisfying Assignment (MMSA).** Given a set $Y$ of boolean variables and a monotone boolean formula $\varphi$, minimize the number of variables assigned to true such that $\varphi$ is satisfied.

We call MMSA$_h$ the MMSA problem restricted to the instances in which
the height of the formula is no more than $h$. In other words, this formula has $h$
levels of altenating AND and OR gates, where the top levels is an AND gate.
MMSA$_2$ is equivalent to the Set Cover problem in which, given a set $\mathcal{X}$ and a
subset $S$ of $2^\mathcal{X}$, we search for a minimum cover of $\mathcal{X}$ with sets of $S$. Therefore,
MMSA$_2$ is NP-Complete [6] and there exists a constant $c$ such that MMSA$_2$
cannot be approximated to within a $c \log(|Y|)$ ratio unless P = NP [4].

<footnote>*Corresponding authors
Email addresses: dimitri.watel@ensiie.fr (Dimitri Watel),
marc-antoine.weisser@centralesupelec.fr (Marc-Antoine Weisser)</footnote>
The following theorem, from Dinur et al. and introduced in [3], is an harder inapproximability result for MMSA<sub>3</sub>.

**Theorem 1 ([3], page 251).** For any $c < \frac{1}{2}$, it is NP-hard to approximate MMSA<sub>3</sub> to within $g_c(n) \stackrel{\text{def}}{=} 2^{\log(n)^{1-\frac{1}{\log \log(n)^c}}}$.

A major drawback with this result is that the parameter $n$ given in this theorem is **not** the size of the MMSA<sub>3</sub> instance. This parameter is instead the size of the problem from which the reduction is done to prove this result. As a consequence, researchers using the Theorem of Dinur et al. to prove an in-approximability result, either cite the theorem without linking the parameter $n$ with their problem (see for example [2]), or must carefully redefine the notations [1, 5].

*Our on contributions.* Firstly, as the Theorem of Dinur et al. is an important theoretical result we deepen the previous work in order to prove that MMSA<sub>3</sub> is hard to approximate to within a ratio depending only on the size of a formula $\varphi$: the number of AND gates $\Lambda$, of OR gates $V$ and the number of boolean variables $|Y|$.

Secondly, we prove a theorem which has a practical potential arising out of the Theorem of Dinur et al.: MMSA<sub>3</sub> is hard to approximate to within any polylogarithmic ratio depending on the number of AND gates, OR gates and the number of variables. This ratio is useful in case of a reduction from MMSA<sub>h</sub> to a problem in which the size depends polynomially on $\Lambda$, $V$ and $|Y|$.

The next section is dedicated to study the function $g_c(n)$ of the Theorem of Dinur et al. Section 3 describes the links between the parameter $n$ and the size of MMSA<sub>3</sub>. Finally, Section 4 contains the proofs of our results.

## 2. The function $g_c(n)$

We prove three useful lemmas about the function $g_c(n)$ of the Theorem of Dinur et al. We first rewrite $g_c(n)$, for some $c \in ]0, \frac{1}{2}]$.

$$ 
\begin{align*}
g_c(n) &= 2^{\log(n)\left(1-\frac{1}{\log \log(n)^c}\right)} \\
&= 2^{\log(n)\cdot\log(n)\left(-\frac{1}{\log \log(n)^c}\right)} \\
&= 2^{\log(n)\cdot 2^{-(\log \log(n))^{1-c}}}
\end{align*}
$$

We firstly show that, on the first hand, it is asymptotically dominated by all the polynomials and, on the other hand, that it asymptotically dominates all the polylogarithms.

**Lemma 2.** Let $\delta > 0$ and $0 < c < \frac{1}{2}$, then $g_c(n) = o(n^\delta)$.
PROOF. Let $0 < c < \frac{1}{2}$ and $\delta > 0$, we are interested in the limit of $\frac{g_c(n)}{n^\delta}$ as $n$ approaches infinity.

$$ \frac{g_c(n)}{n^\delta} = \frac{2^{\log(n) \cdot 2^{-(\log \log(n))^{1-c}}}}{2^{\log(n)\delta}} \\ = 2^{\log(n) \cdot (2^{-(\log \log(n))^{1-c}})^{-\delta}} \quad (1) $$

As $1-c > 0$

$$ \lim_{n \to +\infty} -(\log \log(n))^{1-c} = -\infty $$

$$ \lim_{n \to +\infty} 2^{-(\log \log(n))^{1-c}} - \delta = -\delta $$

$$ \lim_{n \to +\infty} \log(n) \cdot (2^{-(\log \log(n))^{1-c}} - \delta) = -\infty $$

By Equation (1)

$$ \lim_{n \to +\infty} \frac{g_c(n)}{n^\delta} = 0 $$

□

**Lemma 3.** Let $\delta > 0$ and $0 < c < \frac{1}{2}$, then $\log(n)^\delta = o(g_c(n))$.

PROOF. Let $0 < c < \frac{1}{2}$ and $\delta > 0$.

We now give the limit of $\frac{\log^\delta(n)}{g_c(n)}$ as $n$ approaches infinity.

$$ \frac{\log^\delta(n)}{g_c(n)} = \frac{2^{\log \log(n) \cdot \delta}}{2^{\log(n) \cdot 2^{-(\log \log(n))^{1-c}}}} \\ = 2^{\log \log(n) \cdot \left(\delta - \left(\frac{\log(n) \cdot 2^{-(\log \log(n))^{1-c}}}{\log \log(n)}\right)\right)} \quad (2) $$

$$ \frac{\log(n) \cdot 2^{-(\log \log(n))^{1-c}}}{\log \log(n)} = 2^{\log \log(n) - (\log \log(n))^{1-c} - \log \log \log(n)} \\ = 2^{\log \log(n) \cdot \left(1 - \frac{1}{(\log \log(n))^c} - \frac{\log \log \log(n)}{\log \log(n)}\right)} \quad (3) $$

However, as $c > 0$

$$ \lim_{n \to +\infty} \frac{1}{(\log \log(n))^c} = 0 $$
Moreover, as log log log is asymptotically dominated by log log

$$ \lim_{n \to +\infty} \frac{\log \log \log(n)}{\log \log(n)} = 0 $$

As a consequence,

$$ \lim_{n \to +\infty} \log \log(n) \cdot \left( 1 - \frac{1}{(\log \log(n))^c} - \frac{\log \log \log(n)}{\log \log(n)} \right) = +\infty $$

Consequently, by Equation (3)

$$ \lim_{n \to +\infty} \frac{\log(n) \cdot 2^{-(\log \log(n))^{1-c}}}{\log \log(n)} = +\infty $$

$$ \lim_{n \to +\infty} \log \log(n) \cdot \left( \delta - \frac{\log(n) \cdot 2^{-(\log \log(n))^{1-c}}}{\log \log(n)} \right) = -\infty $$

Finally, by Equation (2)

$$ \lim_{n \to +\infty} \frac{\log^{\delta}(n)}{g_c(n)} = 0 $$

□

The following lemma shows a useful property of $g_c(n)$ that is used later in this paper.

**Lemma 4.** Let $c < \frac{1}{2}$, $|F| = \Theta(g_c(n))$ and $D = O((\log \log(n))^c)$, then $|F|^D = o(n)$.

**PROOF.** There are four constants $c_F$, $n_F$, $c_D$ and $n_D$ such that, for all $n \ge n_D$ and $n \ge n_F$

$$ |F| \le c_F \cdot g_c(n) $$

$$ D \le c_D (\log \log(n))^c $$

Consequently

$$ \frac{|F|^D}{n} \le \left(c_F^{c_D \cdot (\log \log(n))^c}\right) \cdot \left(2^{\log(n) \cdot 2^{-(\log \log(n))^{1-c}}} \cdot (c_D \cdot (\log \log(n))^c)\right) \cdot \frac{1}{n} $$

$$ \frac{|F|^D}{n} \le \left(2^{c_D \cdot \log(c_F)} \cdot (\log \log(n))^c\right) \cdot \left(2^{c_D \cdot \log(n) \cdot 2^{-(\log \log(n))^{1-c} + c \cdot \log \log \log(n)}}\right) \cdot 2^{-\log(n)} $$

$$ \frac{|F|^D}{n} \le 2 \left( \log(n) \cdot \left( \left( c_D \cdot \log(c_F) \cdot \frac{(\log \log(n))^c}{\log(n)} \right) + \left( c_D \cdot 2^{-(\log \log(n))^{1-c} + c \cdot \log \log \log(n)} \right) - 1 \right) \right) $$
As $\lim_{n \to +\infty} \frac{(\log \log(n))^c}{\log(n)} = 0$ and $\lim_{n \to +\infty} -(\log \log(n))^{1-c} + c \cdot \log \log \log(n) = -\infty$

$$ \lim_{n \to +\infty} \left( c_D \cdot \log(c_F) \cdot \frac{(\log \log(n))^c}{\log(n)} + c_D \cdot 2^{-(\log \log(n))^{1-c} + c \cdot \log \log \log(n)} - 1 \right) = -1 $$

$$ \lim_{n \to +\infty} 2 \left( \log(n) \cdot \left( \left( c_D \cdot \log(c_F) \cdot \frac{(\log \log(n))^c}{\log(n)} \right) + c_D \cdot 2^{-(\log \log(n))^{1-c} + c \cdot \log \log \log(n)} - 1 \right) \right) = 0 $$

Consequently, $\lim_{n \to +\infty} \frac{|F|^D}{n} = 0$. $\square$

### 3. The reduction

In this section, we describe the parameters of the formula $\varphi$ with the parameter $n$ given in the Theorem of Dinur et al.

We use in this section the same notations as the ones describes in [3]. The given reduction is from the PCP theorem. The parameters of the PCP instance are $n \in \mathbb{N}$, $c < \frac{1}{2}$, $c' < c$, $D = O((\log \log(n))^c)$, $|F| = \Theta(g_{c'}(n))$.

The following MMSA$_3$ instance is built where $T(x, \psi', r|x)$ is a variable.

$$ \varphi = \bigwedge_{\psi \in \Psi} \bigvee_{r \in R_{\psi}} \bigwedge_{x \in \psi} \bigwedge_{\psi' \in \Psi_x} T(x, \psi', r|x) $$

The parameters satisfy: $|\Psi| = n$, $|R_{\psi}| = |F|^D$, $|\psi| = D$, $|\Psi_x| = n$ and the set $T$ contains $n|F|^D$ variables. By Lemma 4, $|R_{\psi}|$ is polynomial.

**Remark 1.** Note that there are 4 levels in this formula, however the levels 3 and 4 are two AND Gates levels and can be merged into one level.

Any $g_c(n)$-approximation for MMSA$_3$ could be used to solve the PCP instance in polynomial time and this proves the Theorem of Dinur et al.

**Lemma 5.** Let $\varepsilon > 0$, then $\Lambda = O(n^{2+\varepsilon})$, $V = n$ and $|Y| = O(n^{1+\varepsilon})$.

**PROOF.** The AND root gate of $\varphi$ has $|\Psi| = n$ children. Any OR gate has $|R_{\psi}| = |F|^D$ children. The AND gates of level 3 and 4 have respectively $|\psi| = D$ and $|\Psi_x| = n$ children. The number of variables of $\varphi$ is $|T| = n|F|^D$.

Consequently, $\Lambda = 1 + n|F|^D(1+D)$, $V = n$ and $|Y| = n|F|^D$. The result for $V$ is proven. We now have to detail the values of $n|F|^DD$ and $n|F|^D$.

Let $0 < \delta < \varepsilon$, by Lemma 2

$$ \begin{aligned} |F| &= \Theta(g_{c'}(n)) = O(n^{\delta}) \\ n|F|^D &= O(n^{1+\delta}(\log \log(n))^c) \\ n|F|^D &= O(n^{1+\delta}(\log \log(n))^c) \\ n|F|^D &= O(n^{1+\varepsilon}) \end{aligned} $$
This gives the result for $|Y|$.

By Lemma 4

$$ 
\begin{align*}
|F|^D &= o(n) \\
n|F|^DD &= O(n^2(\log \log(n))^c) \\
n|F|^DD &= O(n^{2+\epsilon})
\end{align*}
$$

And this gives the result for $\Lambda$ and concludes the proof. $\square$

### 4. Main result

This section is dedicated to proving the main results of this paper. The first theorem is a rewriting of the theorem of [3] with the parameters $\Lambda$, $V$ and $|Y|$ using the results of Lemma 5.

**Theorem 6.** For all $\epsilon > 0$ and $c > \frac{1}{2}$, it is NP-hard to approximate $MMSA_3$ to within $\max(g_c(\sqrt[2+\epsilon]{\Lambda}), g_c(V), g_c(\sqrt[1+\epsilon]{|Y|}))$.

**PROOF.** The proof for $g_c(V)$ is immediate by Lemma 5. We now prove that there is no $g_c(\sqrt[1+\epsilon]{|Y|})$-approximation. The last result is similar. Lemma 5 proves that $|Y| = O(n^{1+\epsilon})$. As $g_c$ is a non-decreasing function, $g_c(\sqrt[1+\epsilon]{|Y|}) \le g_c(O(n))$. The conclusion follows from the property that $\lim_{n \to +\infty} \frac{g_c(O(n))}{g_c'(n)} = 0$ for every $c' \in ]c; \frac{1}{2}[$: a $g_c(\sqrt[1+\epsilon]{|Y|})$-approximation would lead to a $g_c'(n)$-approximation and this is a contradiction by the Theorem of Dinur et al. $\square$

The second theorem is a more easily to use theorem arising out of the Theorem of Dinur et al. It proves MMSA cannot be approximated to within a polylogarithmic ratio.

**Theorem 7.** Let $Q$ be a polynomial with three variables. Unless $P = NP$, there is no polynomial approximation with ratio $Q(\log(|Y|), \log(\Lambda), \log(V))$ for $MMSA_3$.

**PROOF.** The proof is given for the following polynomial $Q(x, y, z) = x^\delta$, for some $\delta > 0$. The proof for other polynomials are similar.

We assume that there is a $Q(\log(|Y|))$-approximation for $MMSA_3$.

Let now be a PCP instance of size $n$ and $0 < c' < c < \frac{1}{2}$. We build an instance of $MMSA_3$ such that $|Y(n)| = O(n^{1+\epsilon})$ by Lemma 5. Thus

(A) for all $\epsilon > 0$, there are two constants $k_\epsilon > 0$ and $n_\epsilon \in \mathbb{N}$ such that, for every integer $n > n_\epsilon$, $|Y(n)| \le k_\epsilon \cdot n^{1+\epsilon}$.

For all $\delta' > \delta$, $\log^\delta$ is asymptotically dominated by $\log^{\delta'}$, consequently:
(B) for all $\varepsilon > 0$, $k_\varepsilon > 0$, $\delta' > \delta$, there is an integer $n' = n(\varepsilon, k_\varepsilon, \delta') \in \mathbb{N}$ such that for every integer $n > n'$, $(\log(k_\varepsilon) + (1 + \varepsilon) \log(n))^\delta < \log^{\delta'}(n)$.

Finally, by Lemma 3, for all $0 < c < \frac{1}{2}$ and $\delta' > 0$, $g_c(n)$ asymptotically dominates $\log^{\delta'}(n)$, thus

(C) for all $\delta' > 0$, there is an integer $n_{\delta'} \in \mathbb{N}$ such that for every integer $n > n_{\delta'}$, $\log^{\delta'}(n) < g_c(n)$.

We are going to use those three properties to prove the inapproximability result. Let $\varepsilon > 0$ and $\delta' > \delta$ be two real numbers. The constants $k_\varepsilon$, $n_\varepsilon$, $n' = n(\varepsilon, k_\varepsilon, \delta')$ and $n_{\delta'}$ are given by the previous properties. We focus on the PCP instances such that $n > \max(n_\varepsilon, n', n_{\delta'})$.

$$Q(\log(|Y(n)|)) = \log^{\delta}(|Y(n)|)$$

By Property (A)

$$Q(\log(|Y(n)|)) \leq \log^{\delta}(k_{\varepsilon} \cdot n^{1+\varepsilon})$$

$$Q(\log(|Y(n)|)) \leq (\log(k_{\varepsilon}) + (1 + \varepsilon) \log(n))^{\delta}$$

By Property (B)

$$Q(\log(|Y(n)|)) \leq \log^{\delta'}(n)$$

By Property (C)

$$Q(\log(|Y(n)|)) \leq g_c(n)$$

As a consequence, there would be $g_c(n)$-approximation for the MMSA$_3$ problem, and this would be a contradiction by the Theorem of Dinur et al. □

A consequence of such a result is that, if we now consider a reduction from MMSA$_h$ to a problem $\Pi$ such that

* the size $s$ of the instances of $\Pi$ is a polynomial in $|Y|$, $\Lambda$ and $V$;

* the reduction proves $\Pi$ cannot be approximated to within $Q(\log(|Y|), \log(\Lambda), \log(V))$ for any polynomial $Q$ with Theorem 7,

then we can prove $\Pi$ cannot be approximated to within $Q'(\log(s))$ for any polynomial $Q'$.
5. Conclusion

In this paper we deepened the inapproximability result of MMSA$_3$ presented
in [3] and gave a new inapproximability ratio only depending on the size of
a formula. This allows researchers to have a pratical use of this important
theoretical result.

[1] CARR, R., DODDI, S., KONJEVOD, G., AND MARATHE, M. On the red-blue set cover problem. In *In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms* (2000), Society for Industrial and Applied Mathematics, pp. 345—353.

[2] CHINCHANI, R., HA, D., IYER, A., NGO, H. Q., AND SHAMBHU, U. On the Hardness of Approximating the Min-Hack Problem. *Journal of Combinatorial Optimization* 9, 3 (2005), 295–311.

[3] DINUR, I., AND SHMUEL, S. On the hardness of approximating label-cover. *Information Processing Letters* 89, 5 (mar 2004), 247–254.

[4] FEIGE, U. A threshold of $ln n$ for approximating set cover. *Journal of the ACM (JACM)* 45, 4 (1998), 634–652.

[5] GRUBER, A. G. Algorithmic and complexity results for boolean and pseudo-boolean functions.

[6] KARP, R. Reducibility among combinatorial problems. In *Complexity of Computer Computations*. Springer, 1972, pp. 85–103.