College Publications logo   College Publications title  
View Basket
Homepage Contact page
   
 
AiML
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
IfColog series in Computational Logic
IfColog Lecture series
IfColog Proceedings
Journals
Journal of Applied Logics - IfCoLoG Journal of Logics and their Applications
About
Editorial Board
Scope of the Journal
Submissions
Forthcoming papers
Law and Society
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 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–2018 College Publications / VFH webmaster