In this paper we consider a set of max-atoms (SMA) that is a set of conjunctions
of m inequalities of the form xi ≤ a + max(xj , xk ) with offset a ∈ R and xi , xj , xk are
the variables elements of the whole set V = {x1 , . . . , xn }. Considering the one-to-one
correspondance of max-atoms and offsets the number of elements of the possibly multiset
of offsets is m. The SMA has always the vector of variables x = (−∞) as trivial solution.
On this object we study two questions. MAP: can we find at least one non trivial solution
to the SMA in strongly polynomial time ? and MAPall: can we find all the solutions of the
SMA in strongly polynomial time ?
We distinguish two cases w.r.t the hypothesis (W): there exists at least one strictly negative
max-atom, ie an inequality xi ≤ a + max(xj , xk ) with a < 0.
When (W) is false there exists at least the non trivial solution x = (0) to the SMA,
indeed 0 ≤ a + max(0, 0) ∀a ≥ 0. And MAP is yes.
When (W) is true we prove in this paper that MAPall is yes with complexity O(mn3 ). And
thus MAP is also yes. So in all cases MAP is yes with time complexity max(O(1), O(mn3 )) =
O(mn3 )).
The important consequence of this result is that the following six PTIME equiva-
lent problems to MAP which are known to be in NP intersection co-NP are also strongly
polynonial. P1: Looking for non trivial solutions of a tropical cone, P2: Computation
of a tropical rank of a matrix, P3: Computation of optimal strategies in parity games
(typically: Mean Payoff Games), P4: Scheduling with and/or precedence constraints, P5:
Shortest path problem in hypergraph, P6: Model checking and µ-calculus.
The whole method developed in this paper is illustrated on an example of SMA which
is PTIME equivalent to P5.