The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems

DOI10.1145/2933575.2934544zbMATH Open1401.68108arXiv1602.04353OpenAlexW2276690803WikidataQ130957550 ScholiaQ130957550MaRDI QIDQ4635922FDOQ4635922

Authors: Libor Barto, Michael Pinsker 

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)

Abstract: We prove that an $omega$-categorical core structure primitively positively interprets all finite structures with parameters if and only if some stabilizer of its polymorphism clone has a homomorphism to the clone of projections, and that this happens if and only if its polymorphism clone does not contain operations $alpha$, $$, $s$ satisfying the identity $$. This establishes an algebraic criterion equivalent to the conjectured borderline between P and NP-complete CSPs over reducts of finitely bounded homogenous structures, and accomplishes one of the steps of a proposed strategy for reducing the infinite domain CSP dichotomy conjecture to the finite case. Our theorem is also of independent mathematical interest, characterizing a topological property of any $omega$-categorical core structure (the existence of a continuous homomorphism of a stabilizer of its polymorphism clone to the projections) in purely algebraic terms (the failure of an identity as above).

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

Recommendations

• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• \( \omega \)-categorical structures avoiding height 1 identities
• Complexity of infinite-domain constraint satisfaction
• Equivalence constraint satisfaction problems

zbMATH Keywords

constraint satisfaction problemhomogeneous structurestabilizerterm conditiondichotomy conjecturepolymorphism clone\(\omega\)-categorical structurecontinuous clone homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Applications of universal algebra in computer science (08A70)

Cited In (41)

• The number of clones determined by disjunctions of unary relations
• Equivalence constraint satisfaction problems
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• PROJECTIVE CLONE HOMOMORPHISMS
• Title not available (Why is that?)
• CORES OVER RAMSEY STRUCTURES
• An algebraic preservation theorem for \(\aleph_0\)-categorical quantified constraint satisfaction
• Reconstructing the topology of clones
• Time complexity of constraint satisfaction via universal algebra
• Title not available (Why is that?)
• Computational Short Cuts in Infinite Domain Constraint Satisfaction
• Loop conditions for strongly connected digraphs
• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
• Pseudo‐loop conditions
• An algebraic preservation theorem for aleph-zero categorical quantified constraint satisfaction
• A dichotomy for first-order reducts of unary structures
• Title not available (Why is that?)
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• Permutation groups with small orbit growth
• A counterexample to the reconstruction of \(\omega\)-categorical structures from their endomorphism monoid
• \( \omega \)-categorical structures avoiding height 1 identities
• Constraint satisfaction problems over numeric domains
• Complexity classification transfer for CSPs via algebraic products
• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• Title not available (Why is that?)
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• A uniform Birkhoff theorem
• The language of stratified sets is confluent and strongly normalising
• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• Absorption in universal algebra and CSP
• Forbidden tournaments and the orientation completion problem
• The local loop lemma
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• General lower bounds and improved algorithms for infinite-domain CSPs
• Reconstructing the topology on monoids and polymorphism clones of the rationals
• Solving equation systems in ω-categorical algebras
• Constraint satisfaction problems for reducts of homogeneous graphs
• ASNP: a tame fragment of existential second-order logic

This page was built for publication: The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635922)