Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)

DOI10.1137/18M1216213MaRDI QIDQ5222129zbMATH OpenWikidataFDO

Authors Libor Barto, Michael Pinsker

Publication date 1 April 2020

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

constraint satisfaction problemdichotomy conjectureomega-categorical structurepointwise convergence topologypolymorphismSiggers identity

Mathematics Subject Classification ID

Equational classes, universal algebra in model theory (03C05) Categoricity and completeness of theories (03C35) 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) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Abstract: The tractability conjecture for finite domain Constraint Satisfaction Problems (CSPs) stated that such CSPs are solvable in polynomial time whenever there is no natural reduction, in some precise technical sense, from the 3-SAT problem; otherwise, they are NP-complete. Its recent resolution draws on an algebraic characterization of the conjectured borderline: the CSP of a finite structure permits no natural reduction from 3-SAT if and only if the stabilizer of the polymorphism clone of the core of the structure satisfies some nontrivial system of identities, and such satisfaction is always witnessed by several specific nontrivial systems of identities which do not depend on the structure. The tractability conjecture has been generalized in the above formulation to a certain class of infinite domain CSPs, namely, CSPs of reducts of finitely bounded homogeneous structures. It was subsequently shown that the conjectured borderline between hardness and tractability, i.e., a natural reduction from 3-SAT, can be characterized for this class by a combination of algebraic and topological properties. However, it was not known whether the topological component is essential in this characterization. We provide a negative answer to this question by proving that the borderline is characterized by one specific algebraic identity, namely the pseudo-Siggers identity $$. This accomplishes one of the steps of a proposed strategy for reducing the infinite domain CSP dichotomy conjecture to the finite case. Our main 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

• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• The complexity of some topological inference problems
• scientific article; zbMATH DE number 1416397
• scientific article; zbMATH DE number 4012593
• Complexity of infinite-domain constraint satisfaction
• scientific article; zbMATH DE number 3938569
• scientific article; zbMATH DE number 4002078

Cites work

• H-coloring dichotomy revisited
• A counterexample to the reconstruction of -categorical structures from their endomorphism monoid
• A dichotomy for first-order reducts of unary structures
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Absorption in universal algebra and CSP
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Constraint Satisfaction with Countable Homogeneous Templates
• Cores of Countably Categorical Structures
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• Existence theorems for weakly symmetric operations
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Non-dichotomies in Constraint Satisfaction Complexity
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• PROJECTIVE CLONE HOMOMORPHISMS
• Reconstructing the topology of clones
• Reducts of Ramsey structures
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• The complexity of phylogeny constraint satisfaction problems
• The complexity of temporal constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The constraint satisfaction problem and universal algebra
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• The structure of finite algebras
• The weakest nontrivial idempotent equations
• The wonderland of reflections
• Topological Birkhoff
• Uniform Birkhoff
• Universal algebra. Fundamentals and selected topics
• Varieties Obeying Homotopy Laws

Cited in

(25)

• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
• Constraint satisfaction, irredundant axiomatisability and continuous colouring
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• A dichotomy for first-order reducts of unary structures
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• PROJECTIVE CLONE HOMOMORPHISMS
• CORES OVER RAMSEY STRUCTURES
• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• \( \omega \)-categorical structures avoiding height 1 identities
• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• Pseudo‐loop conditions
• Constraint satisfaction problems for reducts of homogeneous graphs
• Topological Birkhoff
• CLAP: A New Algorithm for Promise CSPs
• 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
• Hrushovski's encoding and -categorical CSP monsters
• An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
• Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
• A complexity dichotomy in spatial reasoning via Ramsey theory
• Smooth approximations and relational width collapses

This page was built for publication: Topology Is Irrelevant (In a 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 Q5222129)