Name
Abstract | ||
|---|---|---|
A semilinear relation is 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 ∩ , which is not known for max-closed semilinear constraints. Semilinear relations that are max-closed and additionally closed under translations have been called in the literature. One of our main results is a new duality for open tropically convex relations, which puts the CSP for tropically convex semilinear constraints in general into ∩ . 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 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 ; 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 in the sense that as soon as a single relation that is not max-closed is added to , the CSP becomes -hard. |
Year | DOI | Venue |
|---|---|---|
2018 | https://doi.org/10.1007/s00224-017-9762-0 | Theory Comput. Syst. |
Keywords | Field | DocType |
Tropical convexity,Semi-linear relations,Max-closure,Constraint satisfaction,Max-plus-average inequalities,Stochastic games,Piecewise linear constraints,Computational complexity | Discrete mathematics,Constraint satisfaction,Combinatorics,Finite set,Constraint satisfaction problem,Regular polygon,Duality (optimization),Linear inequality,Mathematics,Stochastic game,Computational complexity theory | Journal |
Volume | Issue | ISSN |
62 | 3 | 1432-4350 |
Citations | PageRank | References |
1 | 0.37 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel Bodirsky | 1 | 644 | 54.63 |
| Marcello Mamino | 2 | 16 | 5.51 |