


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 PosetSAT($Phi$) where $Phi$ is a given set of quantifierfree $leq$formulas. An instance of PosetSAT($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 NPcomplete or in P, depending on the constraint language $Phi$.
All PosetSAT problems can be formalized as constraint satisfaction problems of reducts of the random partial order. We use modeltheoretic 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.


