A complexity dichotomy for poset constraint satisfaction

Abstract

In this paper we determine the complexity of a broad class of problems that extends the temporal constraint satisfaction problems. To be more precise we study the problems Poset-SAT($Φ$), where $Φ$ is a given set of quantifier-free $\leq$-formulas. An instance of Poset-SAT($Φ$) consists of finitely many variables $x_1,\ldots,x_n$ and formulas $ϕ_i(x_{i_1},\ldots,x_{i_k})$ with $ϕ_i \in Φ$; the question is whether this input is satisfied by any partial order on $x_1,\ldots,x_n$ or not. We show that every such problem is NP-complete or can be solved in polynomial time, depending on $Φ$. All Poset-SAT problems can be formalized as constraint satisfaction problems on 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.