A complexity dichotomy for poset constraint satisfaction

DOI10.4230/LIPICS.STACS.2017.47MaRDI QIDQ4636647zbMATH OpenFDO

Authors Michael Kompatscher, Trung van Pham

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1603.00082

zbMATH Keywords

computational complexityconstraint satisfactionRamsey theoryrandom partial orderuniversal algebra

Mathematics Subject Classification ID

Categoricity and completeness of theories (03C35) Ramsey theory (05D10) Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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($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 $ph{i}_i(x_{i_1},ldots,x_{i_k})$ with $ph{i}_{i}inPhi$; 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.

Recommendations

• A complexity dichotomy for poset constraint satisfaction
• The complexity of temporal constraint satisfaction problems
• scientific article; zbMATH DE number 1962829
• Non-dichotomies in Constraint Satisfaction Complexity

Cited in

(17)

• Constants and finite unary relations in qualitative constraint reasoning
• Using model theory to find decidable and tractable description logics with concrete domains
• Itemset frequency satisfiability: complexity and axiomatization
• scientific article; zbMATH DE number 1962829 (Why is no real title available?)
• A dichotomy for first-order reducts of unary structures
• The language of stratified sets is confluent and strongly normalising
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
• Tractable combinations of temporal CSPs
• Some new decidability results on positive and negative set constraints
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• \( \omega \)-categorical structures avoiding height 1 identities
• A complexity dichotomy for poset constraint satisfaction
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• An order out of nowhere: a new algorithm for infinite-domain CSPs
• Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
• Three fundamental questions in modern infinite-domain constraint satisfaction

This page was built for publication: A complexity dichotomy for poset constraint satisfaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636647)