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

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

  • Manuel Bodirsky - , Institute of Algebra, TUD Dresden University of Technology (Author)
  • Antoine Mottet - , Charles University Prague (Author)
  • Miroslav Olsak - , Charles University Prague (Author)
  • Jakub Oprsal - , Durham University (Author)
  • Michael Pinsker - , Charles University Prague, Vienna University of Technology (Author)
  • Ross Willard - , University of Waterloo (Author)

Abstract

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable when the model-complete core of the template has a pseudo-Siggers polymorphism, and NP-complete otherwise. One of the important questions related to this conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed 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 nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ 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.

Details

Original languageEnglish
Title of host publication2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
ISBN (electronic)9781728136080
Publication statusPublished - Jun 2019
Peer-reviewedYes

Conference

Title34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019
Duration24 - 27 June 2019
CityVancouver
CountryCanada

External IDs

ORCID /0000-0001-8228-3611/work/142241066

Keywords

ASJC Scopus subject areas