A COMPLEXITY DICHOTOMY FOR POSET CONSTRAINT SATISFACTION

被引：0

作者：

Kompatscher, Michael ^{[1
]}

Trung Van Pham ^{[2
]}

机构：

[1] MFF UK, Dept Algebra, Sokolovska 83, Prague 18600 8, Czech Republic

[2] Vietnam Acad Sci & Technol, Dept Math Comp Sci, Inst Math, Hanoi, Vietnam

来源：

JOURNAL OF APPLIED LOGICS-IFCOLOG JOURNAL OF LOGICS AND THEIR APPLICATIONS | 2018年 / 5卷 / 08期

基金：

奥地利科学基金会;

关键词：

constraint satisfaction; random partial order; homogeneous structures; model theory; polymorphism clones;

D O I：

暂无

中图分类号：

B81 [逻辑学（论理学）];

学科分类号：

010104 ; 010105 ;

摘要：

In this paper we determine the complexity of a broad class of problems that extend the temporal constraint satisfaction problems classified by Bodirsky and Kara. To be more precise, we study problems Poset-SAT(Phi) where Phi is a given set of quantifier-free <=-formulas. An instance of Poset-SAT(Phi) then consists of finitely many variables and constraints on them expressible in Phi; the question is then whether this input can be satisfied in some partial order or not. We show that every such problem is either NP-complete or in P, depending on the constraint language Phi. All Poset-SAT problems can be formalized as constraint satisfaction problems of 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.

引用

页码：1663 / 1695

页数：33