Complexity of comparing expressions in max-plus algebra

Max-plus algebra has been widely used in the study of discrete-event dynamic systems.Using max-plus algebra makes it easy to specify safety constraints on events since they can be described as a set of inequalities of state variables,i.e.,firing times of relevant events.This paper proves that the problem of solving max-plus inequalities in a cube(MAXINEQ)is nondeterministic polynomial-time hard(NP-hard)in strong sense and the problem of verifying max-plus inequalities(VERMAXINEQ)is co-NP.As a corollary,the problem of solving a system of multivariate max-algebraic polynomial equalities and inequalities(MPEI)is shown to be NP-hard in strong sense.The results indicate the difficulties in comparing max-plus formulas in general.Problem structures of specific systems have to be explored to enable the development of efficient algorithms.