1
$\begingroup$

Suppose that we have two sums: a1+a2+...+an, b1+b2+...+bm

We can perform only two binary operations on operands of these sums:

  • lt (less than)
  • eq (equal)

These operations can return 3 possible results: true, false, unknown. Other operations like summation, subtraction and etc. are not allowed.

The question is how to implement algorithm for function lt(a1+a2+...+an, b1+b2+...+bm), that also returns true, false or unknown? But unknown can be returned only if there is no enough information to return true or false.

For example if we know that (n=m=3 && a1 < b3 && a2 = b2 && a3 < b1) the algorithm have to return true. Or if we know that (n=3 && m=2 && a1 < b1 && a2 < b1 && a3 < b2 && b1 < b2) the algorithm have to return unknown.

$\endgroup$
3
  • $\begingroup$ Your requirements are unclear, in particular, it is unclear what the desired output from the function should be, in general. If I propose the function that always returns "unknown", that sounds like it might meet all stated requirements, but I doubt you'll be satisfied with it. That makes me suspect that the requirements have not been fully and unambiguously specified. An example is not a substitute for a general statement of the task. What's the context in which you encountered this question? Is there a motivation, or an external source where you saw it? $\endgroup$
    – D.W.
    Feb 12, 2021 at 19:55
  • $\begingroup$ Possibly relevant: math.tau.ac.il/~nogaa/PDFS/boltsp2.pdf $\endgroup$
    – D.W.
    Feb 12, 2021 at 19:58
  • $\begingroup$ @D.W. Thank you I'l read this article. About requirements, you right they are not clear enough. I think that precise requirement would be to return unknown only if there is not enough information to return true or false. The context is next. A complex math expression is passed to my program and my program have to simplify this expression. To do this I have to know properties of parts of this expression. For example I can simplify expression like max(a, b, c) to a if I know, that a>=b>=c , where a,b,c can be arbitrary expressions (for example it can be sums). $\endgroup$
    – aggravator
    Feb 12, 2021 at 20:25

1 Answer 1

0
$\begingroup$

I will assume your variables can take on arbitrarily real numbers. Build a weighted directed graph that represents all known inequalities, with one vertex per element (i.e., $n+m$ vertices in total). In particular, apply 'eq' and 'lt' to all ${n+m \choose 2}$ pairs of elements. Then:

  • If $x < y$ (i.e., $\textsf{lt}(x,y)$ returns true), where $x,y$ are two elements, add a directed edge $x \to y$ with length $-1$.

  • If $x \le y$ (i.e., $\textsf{lt}(y,x)$ returns false), add a directed edge $x \to y$ with length 0.

  • If $x=y$ (i.e., $\textsf{eq}(x,y)$ returns true), then add directed edges $x \to y$ and $y \to x$ with length 0.

  • If $x\ne y$ (i.e., $\textsf{eq}(x,y)$ returns false), do nothing and add no edges.

Let $d(x,y)$ be the length of the shortest path from $x$ to $y$ in this graph. If $d(x,y)=c$, then we will be guaranteed that $x \le y + c$, and this is the optimal $c$ for which this is true (i.e., it is the smallest $c$ for which this is true).

Compute a new bipartite graph $G$ with an edge $a_i\to b_j$ of length $d(a_i,b_j)$ for each $a_i,b_j$. This can be computed with the Floyd-Warshall algorithm, for example.

Find the minimum-weight perfect matching in this bipartite graph. This is an instance of the assignment problem, and hence can be solved in polynomial time with standard algorithms. If the total weight of the matching is $w$, then we can conclude that

$$a_1+\dots+a_n \le b_1+\dots+b_m + w.$$

Consequently, if $w \le 0$, then we can conclude that $a_1+\dots+a_n \le b_1+\dots+b_m$ and we can return "true" to the original question.

Solve another assignment problem for the bipartite graph with edges $b_j \to a_i$ of length $d(a_i,b_j)$ for each $a_i,b_j$. In this way, we obtain $w'$ such that

$$b_1+\dots+b_m \le a_1+\dots+a_n + w'.$$

If $w' \le 0$, return "false" to the original question.

Otherwise, return "unknown".

This takes $O(nm)$ calls to the binary operations and $O((nm)^{2.5} \log n)$ running time.

This works for this very specific problem. A more general approach is to use linear programming: if you want to check whether $(I_1 \land \cdots \land I_k) \implies J$, where the $I$'s and $J$ are linear inequalities, then check whether the system of inequalities $I_1 \land \cdots \land I_k \land \neg J$ is satisfiable using linear programming. This will let you support more general mathematical expressions and more general relationships between the variables, as long as they are all linear functions/inequalities of the variables. In your problem, after you call 'lt' and 'eq' on all pairs of elements, each operation that returns something other than "unknown" gives you an inequality or equality $I_i$ on two variables. Here $J$ is the inequality $a_1+\dots+a_n \le b_1+\dots+b_m$. So, you could apply linear programming directly to your problem. This approach also supports more general operations, as long as they are all linear.

My answer above essentially solved the linear programming problem for the special case where $I_1,\dots,I_k$ are all inequalities with a difference of two variables, and $J$ has the form $a_1+\dots+a_n \le b_1+\dots+b_m$. I used a standard data structure for representing differences of two variables (the graph), and then combined it with an algorithm for the assignment problem to capture the one additional inequality with multiple variables.

$\endgroup$
5
  • $\begingroup$ I think there’s a problem. Say a1 < b1 = a2 < b2, but comparing a1 and b2 gives “unknown”. Then removing b1 and a2 removes that relationship. I’d first add such knowledge in. $\endgroup$
    – gnasher729
    Feb 12, 2021 at 22:34
  • $\begingroup$ Thanks! It is really good solution. It seems that it doesn't account for some cases, for example if n=2 && m=2, and we know only that a1<b1 && a2<b1 && b1<b2 (other comparisons give unknown) your alogrithm will not return true, since it doesn't compare bi<bj. But it is quite easy to extend to account for such cases. Honestly, I didn't get how to reduce this task to liner programming. If it is not too laborious can you explain how to form matrix A, vectors c and b for this specific case (if we express lp problem as argmax c^tx subject to Ax<=b, x>=0). $\endgroup$
    – aggravator
    Feb 12, 2021 at 22:36
  • $\begingroup$ @gnasher729, good point. My previous answer was broken, for the reasons you described. See updated answer, which I think fixes those problems. $\endgroup$
    – D.W.
    Feb 13, 2021 at 0:59
  • $\begingroup$ @aggravator, good point. See updated answer, which I think now addresses all of these issues. I also expanded on the relationship to linear programming. $\endgroup$
    – D.W.
    Feb 13, 2021 at 0:59
  • $\begingroup$ @D.W. Thanks again, now I've understood how to reduce problem to lp. $\endgroup$
    – aggravator
    Feb 13, 2021 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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