Hard problems in max-algebra, control theory, hypergraphs and other areas I

We introduce the max-atom problem (MAP): solving (in Z) systems of inequations of the form max(x, y)+ k ≥ z, where x, y, z are variables and k ∈ Z. Our initial motivation for MAP was reasoning on delays in circuits using SAT Modulo Theories [10], viewing MAP as a natural extension of Difference Logic, i.e., inequations of the form x+k ≥ y. Here we show that MAP is PTIME-equivalent to several rather different well-known problems for which no PTIME al-gorithm has been found so far, in spite of decades of indepen-dent efforts. One is on solving two-sided linear max-plus sys-tems (Section 3 of this paper) that arise in Control Theory when modeling Discrete Event Systems, and another one on shortest paths in directed weighted hypergraphs (Section 4). Interestingly, (see Section 2) there is also a simple PTIME equivalence between MAP and a scheduling problem consid