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

\(\omega\)-categorical structureconstraint satisfaction problemcontinuous clone homomorphismdichotomy conjecturehomogeneous structurepolymorphism clonestabilizerterm condition

Mathematics Subject Classification ID

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

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

(47)

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

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)