Skip to main content

Research Repository

Advanced Search

Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)

Bodirsky, Manuel; Mottet, Antoine; Olsak, Miroslav; Oprsal, Jakub; Pinsker, Michael; Willard, Ross

Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems) Thumbnail


Authors

Manuel Bodirsky

Antoine Mottet

Miroslav Olsak

Jakub Oprsal

Michael Pinsker

Ross Willard



Abstract

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (innite) nitely bounded homogeneous structures states that such CSPs are polynomial-time tractable when the modelcomplete core of the template has a pseudo-Siggers polymorphism, and NPcomplete otherwise. One of the important questions related to this conjecture is whether, similarly to the case of nite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a xed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each non-trivial set of height 1 identities a structure whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of non-trivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of non-trivial height 1 identities dier for !-categorical structures with less than double exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures. 1.

Citation

Bodirsky, M., Mottet, A., Olsak, M., Oprsal, J., Pinsker, M., & Willard, R. (2019). Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems). In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). https://doi.org/10.1109/lics.2019.8785883

Conference Name 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Conference Location Vancouver, Canada
Start Date Jun 24, 2019
End Date Jun 27, 2019
Acceptance Date Mar 28, 2019
Online Publication Date Aug 5, 2019
Publication Date Aug 5, 2019
Deposit Date Sep 3, 2019
Publicly Available Date Sep 3, 2019
Publisher Institute of Electrical and Electronics Engineers
Book Title 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
DOI https://doi.org/10.1109/lics.2019.8785883
Public URL https://durham-repository.worktribe.com/output/1142069
Related Public URLs https://arxiv.org/abs/1901.04237

Files

Accepted Conference Proceeding (786 Kb)
PDF

Copyright Statement
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.





You might also like



Downloadable Citations