The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems

DOI10.1145/2933575.2934544zbMath1401.68108arXiv1602.04353OpenAlexW2276690803MaRDI QIDQ4635922

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.04353

zbMATH Keywords

constraint satisfaction problem stabilizer homogeneous structure term condition dichotomy conjecture polymorphism clone \(\omega\)-categorical structure continuous clone homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Operations and polynomials in algebraic structures, primal algebras (08A40)

Related Items (31)

Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting) ⋮ A counterexample to the reconstruction of \(\omega\)-categorical structures from their endomorphism monoid ⋮ When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮ A uniform Birkhoff theorem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Reconstructing the topology of clones ⋮ Unnamed Item ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Reconstructing the topology on monoids and polymorphism clones of the rationals ⋮ Solving equation systems in ω-categorical algebras ⋮ Permutation groups with small orbit growth ⋮ Pseudo‐loop conditions ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Loop conditions for strongly connected digraphs ⋮ Unnamed Item ⋮ The local loop lemma ⋮ Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ The number of clones determined by disjunctions of unary relations ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ PROJECTIVE CLONE HOMOMORPHISMS ⋮ CORES OVER RAMSEY STRUCTURES ⋮ Unnamed Item ⋮ ASNP: a tame fragment of existential second-order logic ⋮ Unnamed Item ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction

This page was built for publication: The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems