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)

• 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
• scientific article; zbMATH DE number 7378350 (Why is no real title available?)
• CORES OVER RAMSEY STRUCTURES
• Reconstructing the topology of clones
• An algebraic preservation theorem for \(\aleph_0\)-categorical quantified constraint satisfaction
• Time complexity of constraint satisfaction via universal algebra
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Computational Short Cuts in Infinite Domain Constraint Satisfaction
• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
• Loop conditions for strongly connected digraphs
• Pseudo‐loop conditions
• An algebraic preservation theorem for aleph-zero categorical quantified constraint satisfaction
• A dichotomy for first-order reducts of unary structures
• Permutation groups with small orbit growth
• A counterexample to the reconstruction of \(\omega\)-categorical structures from their endomorphism monoid
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• \( \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
• scientific article; zbMATH DE number 7406819 (Why is no real title available?)
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
• A uniform Birkhoff theorem
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• 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
• The local loop lemma
• Forbidden tournaments and the orientation completion problem
• 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)