A Complexity Dichotomy for Poset Constraint Satisfaction.

In this paper we determine the complexity of a broad class of problems that extend the temporal constraint satisfaction problems classified by Bodirsky and Kára. To be more precise, we study problems Poset-SAT(Φ) where Φ is a given set of quantifier-free ≤-formulas. An instance of Poset-SAT(Φ) then consists of finitely many variables and constraints on them expressible in Φ; the question is then whether this input can be satisfied in some partial order or not. We show that every such problem is either NP-complete or in P, depending on the constraint language Φ. All Poset-SAT problems can be formalized as constraint satisfaction problems of reducts of the random partial order. We use model-theoretic concepts and techniques from universal algebra to study these reducts. In the course of this analysis we establish a dichotomy that we believe is of independent interest in universal algebra and model theory.

Authors

• Michael Kompatscher
• Trung Van Pham

Keywords

• constraint satisfaction
• random partial order
• homogeneous structures
• model theory
• polymorphism clones