The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems

DOI10.1145/2933575.2934544MaRDI QIDQ4635922zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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).

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

Cited in

(41)

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

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)