Tropically convex constraint satisfaction
Abstract
A semilinear relation S is max-closed if it is preserved by taking the componentwise maximum. The constraint satisfaction problem for max-closed semilinear constraints is at least as hard as determining the winner in Mean Payoff Games, a notorious problem of open computational complexity. Mean Payoff Games are known to be in the intersection of NP and co-NP, which is not known for max-closed semilinear constraints. Semilinear relations that are max-closed and additionally closed under translations have been called tropically convex in the literature. One of our main results is a new duality for open tropically convex relations, which puts the CSP for tropically convex semilinaer constraints in general into NP intersected co-NP. This extends the corresponding complexity result for scheduling under and-or precedence constraints, or equivalently the max-atoms problem. To this end, we present a characterization of max-closed semilinear relations in terms of syntactically restricted first-order logic, and another characterization in terms of a finite set of relations L that allow primitive positive definitions of all other relations in the class. We also present a subclass of max-closed constraints where the CSP is in P; this class generalizes the class of max-closed constraints over finite domains, and the feasibility problem for max-closed linear inequalities. Finally, we show that the class of max-closed semilinear constraints is maximal in the sense that as soon as a single relation that is not max-closed is added to L, the CSP becomes NP-hard.
- Publication:
-
arXiv e-prints
- Pub Date:
- June 2015
- DOI:
- arXiv:
- arXiv:1506.04184
- Bibcode:
- 2015arXiv150604184B
- Keywords:
-
- Computer Science - Computational Complexity;
- 68Q25;
- 15A80;
- 52B55;
- F.4.1;
- F.2.2;
- G.1.6
- E-Print:
- 29 pages, 2 figures