  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($\Phi$), where $\Phi$ is a given set of
quantifier-free $\leq$-formulas. An instance of Poset-SAT($\Phi$) consists of
finitely many variables $x_1,\ldots,x_n$ and formulas
$\phi_i(x_{i_1},\ldots,x_{i_k})$ with $\phi_i \in \Phi$; 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 $\Phi$. 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.
