2026-07-24T17:51:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6985 2024-03-06T10:39:13Z ddc:004 open_access

A Complexity Dichotomy for Poset Constraint Satisfaction Kompatscher, Michael Pham, Trung Van Constraint Satisfaction Random Partial Order Computational Complexity Universal Algebra Ramsey Theory We determine the complexity of all constraint satisfaction problems over partial orders, in particular we show that every such problem is NP-complete or can be solved in polynomial time. This result generalises the complexity dichotomy for temporal constraint satisfaction problems by Bodirsky and Kára. We apply the so called universal-algebraic approach together with tools from model theory and Ramsey theory to prove our result. In the course of this analysis we also establish a structural dichotomy regarding the model theoretic properties of the reducts of the random partial order. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Kompatscher and Trung Van Pham 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.47 urn:nbn:de:0030-drops-69850 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.47 eng https://creativecommons.org/licenses/by/3.0/legalcode