College Publications logo   College Publications title  
View Basket
Homepage Contact page
   
 
AiML
Academia Brasileira de Filosofia
Algorithmics
Cadernos de Lógica e Computação
Cadernos de Lógica e Filosofia
Cahiers de Logique et d'Epistemologie
Communication, Mind and Language
Computing
Cuadernos de lógica, Epistemología y Lenguaje
DEON
Dialogues
Economics
Encyclopaedia of Logic
Filosofia
Handbooks
Historia Logicae
IfColog series in Computational Logic
IfColog Lecture series
IfColog Proceedings
Journal of Applied Logics - IfCoLog Journal
About
Editorial Board
Scope of the Journal
Submissions
Forthcoming papers
Journals
Landscapes
Logics for New-Generation AI
Logic and Law
Logic and Semiotics
Logic PhDs
Logic, Methodology and Philosophy of Science
The Logica Yearbook
Neural Computing and Artificial Intelligence
Philosophy
Research
The SILFS series
Studies in Logic
Studies in Talmudic Logic
Systems
Texts in Logic and Reasoning
Texts in Mathematics
Tributes
Other
Digital Downloads
Information for authors
About us
Search for Books
 



Forthcoming papers


Back

A Complexity Dichotomy for Poset Constraint Satisfaction

Michael Kompatscher and Trung Van Pham

In this paper we determine the complexity of a broad class of problems that extend the temporal constraint satisfaction problems classified by Bodirsky and K'ara. To be more precise, we study problems Poset-SAT($Phi$) where $Phi$ is a given set of quantifier-free $leq$-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.






© 2005–2022 College Publications / VFH webmaster