文章基本信息

标题：A Complexity Dichotomy for Poset Constraint Satisfaction
本地全文：下载
作者：Michael Kompatscher ; Trung Van Pham
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：66
页码：47:1-47:12
DOI：10.4230/LIPIcs.STACS.2017.47
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Constraint Satisfaction; Random Partial Order; Computational Complexity; Universal Algebra; Ramsey Theory