|
|
|
Forthcoming papers
Back
| A Complexity Dichotomy for Poset Constraint Satisfaction
Michael Kompatscher and Trung Van Pham
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'ara. To be more precise, we study problems Poset-SAT($Phi$) where $Phi$ is a given set of quantifier-free $leq$-formulas. An instance of Poset-SAT($Phi$) then consists of finitely many variables and constraints on them expressible in $Phi$; 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 $Phi$.
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.
|
|
|