<p>Your problem is coNP-hard, by reduction from SAT.  In particular, using inequalities <span class="math-container">$x \ge 1$</span>, <span class="math-container">$x \le 0$</span> and interpreting <span class="math-container">$0$</span> as false and <span class="math-container">$1$</span> as true, we can encode any SAT formula <span class="math-container">$\varphi$</span> into this form (each clause <span class="math-container">$\varphi$</span> gets translated into an expression, each literal in the clause is translated into one of the two inequalities listed above, and we take <span class="math-container">$e$</span> to be the expression <span class="math-container">$x \ge 0$</span>, i.e., an expression that is always satisfied).</p>
<p>Moreover, your problem is in coNP and in practice can be solved with a SAT solver.  Let <span class="math-container">$c_{i,1},\dots,c_{i,k}$</span> denote the set of integer constants that appear in some inequality together with the variable <span class="math-container">$x_i$</span>.  Assume <span class="math-container">$c_{i,1},\dots,c_{i,k}$</span> have been put into sorted order.  This defines the intervals <span class="math-container">$(-\infty,c_{i,1}),[c_{i,1},c_{i,1}],(c_{i,1},c_{i,2}),[c_{i,2},c_{i,2}],\dots,(c_{i,k},\infty)$</span>.  Introduce boolean variables <span class="math-container">$v_{i,J}$</span>, one per interval <span class="math-container">$J$</span>, where <span class="math-container">$v_{i,J}$</span> is interpreted as meaning that <span class="math-container">$x_i &lt; J$</span>.  In this way, every inequality can be translated into a disjunction of literals.  We also add the disjunctions <span class="math-container">$\vee_J x_{i,J}$</span> and the <span class="math-container">$\neg x_{i,J_1} \lor \neg x_{i,J_2}$</span> for each <span class="math-container">$i$</span> and each two different intervals <span class="math-container">$J_1,J_2$</span>.  Proceeding in this way we can convert <span class="math-container">$e$</span> into a conjunction of disjunctions, and we can convert <span class="math-container">$\wedge_{f \in E} \neg f$</span> into a conjunction of disjunctions (using the Tseitin transform as needed), and thus convert your problem into a CNF formula, which will be satisfiable iff <span class="math-container">$E$</span> does not cover all of <span class="math-container">$e$</span>.</p>

CC BY-SA 4.0
2022-12-05T10:34:40.257Z
while waiting for an answer, I had already thought about reduction from SAT, nevertheless the details you gave me are very helpful and some of them escaped me. Thank you so much
mahou_2019
CC BY-SA 4.0
2023-01-04T12:12:13.337Z
@mahou_2019, doesn't this answer your question?  If so please mark the answer as accepted, thanks.
Neal Young
CC BY-SA 4.0
2022-12-05T04:07:01.063Z
2022-12-05T04:07:01.063Z
D.W.
<p>Before I can define my problem, let's make a simple definition. An expression <span class="math-container">$e$</span> is a conjunction of inequalities of the form <span class="math-container">$x~ op~ v$</span> where: <span class="math-container">$x$</span> is a variable, <span class="math-container">$op\in[&lt;,&gt;,\leq,\geq,=]$</span>, and <span class="math-container">$v$</span> is an integer value. For instance, the expression <span class="math-container">$e=age\geq 45 \wedge exp\geq 10$</span> aims to find all persons satisfying some conditions over <span class="math-container">$age$</span> and <span class="math-container">$experience$</span>.</p>
<p><span class="math-container">$\textbf{Problem statement:}$</span> Given an expression <span class="math-container">$e$</span> and a set of expressions <span class="math-container">$E=\{e_1,...e_n\}$</span>, is there a subset <span class="math-container">$E_s$</span> of <span class="math-container">$E$</span> that covers all points of <span class="math-container">$e$</span> ? I.e. all results of <span class="math-container">$e$</span> are all returned by <span class="math-container">$E_s$</span>.</p>
<p><span class="math-container">$\underline{Example}:$</span></p>
<p>&quot;<span class="math-container">$e=age\geq 45 \wedge exp\geq 10$</span>&quot;  <span class="math-container">$\textbf{is covered}$</span> by <span class="math-container">$\{e_1,e_2,e_3\}$</span> where:</p>
<p>&quot;<span class="math-container">$e_1=age&gt;30 \wedge age&lt;37 \wedge exp\geq 10$</span>&quot;, &quot;<span class="math-container">$e_2=age\geq 37 \wedge exp &gt; 8 \wedge exp &lt; 15$</span>&quot;, &quot;<span class="math-container">$e_3=age\geq 37 \wedge exp\geq 15$</span>&quot;.</p>
<p><span class="math-container">$\underline{Explanation}:$</span></p>
<p>By merging <span class="math-container">$e_2$</span> with <span class="math-container">$e_3$</span> we obtain the expression &quot;<span class="math-container">$e_{23}=age\geq 37 \wedge exp &gt; 8 $</span>&quot;</p>
<p>By merging <span class="math-container">$e_1$</span> with <span class="math-container">$e_{23}$</span> we obtain the expression &quot;<span class="math-container">$e_{123}=age &gt; 30 \wedge exp &gt; 8 $</span>&quot;</p>
<p>It is clear the <span class="math-container">$e$</span> is <span class="math-container">$\textbf{covered by}$</span> <span class="math-container">$e_{123}$</span>.</p>
<p><span class="math-container">$\textbf{My Question:}$</span> Is there some theoretical problem that can be reduced to this problem ?</p>

CC BY-SA 4.0
2022-12-05T03:47:05.617Z
What do you mean by the "points of $e$"?  What do you mean by the "results of $e$" and "returned by $E_s$"?  Please define these terms.  An example is not a substitute for a clear definition.  Do you mean for every assignment that satisfies $e$ also satisfies one of the expressions in $E_s$?  If so, isn't the question equivalent to asking whether every assignment that satisfies $e$ also satisfies one of the expressions in $E$ (since we can take $E_s=E$)?
D.W.
CC BY-SA 4.0
2022-12-05T03:49:27.340Z
What is your real question?  Do you want to know the complexity of this problem?  What's the motivation or context in which you encountered it?
D.W.
<subset-sum><first-order-logic><embeddings>
reducing this problem to a decision problem
mahou_2019
# reducing this problem to a decision problem

(Asked by: username_0 on 2022-12-04)

Before I can define my problem, let's make a simple definition. An expression $e$ is a conjunction of inequalities of the form $x~ op~ v$ where: $x$ is a variable, $op\in[<,>,\leq,\geq,=]$, and $v$ is an integer value. For instance, the expression $e=age\geq 45 \wedge exp\geq 10$ aims to find all persons satisfying some conditions over $age$ and $experience$.

$\textbf{Problem statement:}$ Given an expression $e$ and a set of expressions $E=\{e\_1,...e\_n\}$, is there a subset $E\_s$ of $E$ that covers all points of $e$ ? I.e. all results of $e$ are all returned by $E\_s$.

$\underline{Example}:$

"$e=age\geq 45 \wedge exp\geq 10$" $\textbf{is covered}$ by $\{e\_1,e\_2,e\_3\}$ where:

"$e\_1=age>30 \wedge age<37 \wedge exp\geq 10$", "$e\_2=age\geq 37 \wedge exp > 8 \wedge exp < 15$", "$e\_3=age\geq 37 \wedge exp\geq 15$".

$\underline{Explanation}:$

By merging $e\_2$ with $e\_3$ we obtain the expression "$e\_{23}=age\geq 37 \wedge exp > 8 $"

By merging $e\_1$ with $e\_{23}$ we obtain the expression "$e\_{123}=age > 30 \wedge exp > 8 $"

It is clear the $e$ is $\textbf{covered by}$ $e\_{123}$.

$\textbf{My Question:}$ Is there some theoretical problem that can be reduced to this problem ?

**Tags:** subset-sum, first-order-logic, embeddings
> **Comments:**
> **username_1**: What do you mean by the "points of $e$"?  What do you mean by the "results of $e$" and "returned by $E_s$"?  Please define these terms.  An example is not a substitute for a clear definition.  Do you mean for every assignment that satisfies $e$ also satisfies one of the expressions in $E_s$?  If so, isn't the question equivalent to asking whether every assignment that satisfies $e$ also satisfies one of the expressions in $E$ (since we can take $E_s=E$)?  
> **username_1**: What is your real question?  Do you want to know the complexity of this problem?  What's the motivation or context in which you encountered it?  

---

## 1 answers

### Answer by username_1 on 2022-12-05. Score: 1 | Accepted answer

Your problem is coNP-hard, by reduction from SAT. In particular, using inequalities $x \ge 1$, $x \le 0$ and interpreting $0$ as false and $1$ as true, we can encode any SAT formula $\varphi$ into this form (each clause $\varphi$ gets translated into an expression, each literal in the clause is translated into one of the two inequalities listed above, and we take $e$ to be the expression $x \ge 0$, i.e., an expression that is always satisfied).

Moreover, your problem is in coNP and in practice can be solved with a SAT solver. Let $c\_{i,1},\dots,c\_{i,k}$ denote the set of integer constants that appear in some inequality together with the variable $x\_i$. Assume $c\_{i,1},\dots,c\_{i,k}$ have been put into sorted order. This defines the intervals $(-\infty,c\_{i,1}),[c\_{i,1},c\_{i,1}],(c\_{i,1},c\_{i,2}),[c\_{i,2},c\_{i,2}],\dots,(c\_{i,k},\infty)$. Introduce boolean variables $v\_{i,J}$, one per interval $J$, where $v\_{i,J}$ is interpreted as meaning that $x\_i < J$. In this way, every inequality can be translated into a disjunction of literals. We also add the disjunctions $\vee\_J x\_{i,J}$ and the $\neg x\_{i,J\_1} \lor \neg x\_{i,J\_2}$ for each $i$ and each two different intervals $J\_1,J\_2$. Proceeding in this way we can convert $e$ into a conjunction of disjunctions, and we can convert $\wedge\_{f \in E} \neg f$ into a conjunction of disjunctions (using the Tseitin transform as needed), and thus convert your problem into a CNF formula, which will be satisfiable iff $E$ does not cover all of $e$.

> **Comments:**
> **username_0**: while waiting for an answer, I had already thought about reduction from SAT, nevertheless the details you gave me are very helpful and some of them escaped me. Thank you so much  
> **username_2**: @mahou_2019, doesn't this answer your question?  If so please mark the answer as accepted, thanks.  

---

