A dichotomy for first-order reducts of unary structures

DOI10.23638/LMCS-14(2:13)2018MaRDI QIDQ4643958zbMATH OpenFDO

Authors Manuel Bodirsky, Antoine Mottet

Publication date 30 May 2018

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

Mathematics Subject Classification ID

Model theory of denumerable and separable structures (03C15) 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: Many natural decision problems can be formulated as constraint satisfaction problems for reducts $mathbbA$ of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. Our first result is a general polynomial-time reduction from such infinite-domain CSPs to finite-domain CSPs. We use this reduction to obtain new powerful polynomial-time tractability conditions that can be expressed in terms of the topological polymorphism clone of $mathbbA$. Moreover, we study the subclass $mathcalC$ of CSPs for structures $mathbbA$ that are reducts of a structure with a unary language. Also this class $mathcalC$ properly extends the class of all finite-domain CSPs. We apply our new tractability conditions to prove the general tractability conjecture of Bodirsky and Pinsker for reducts of finitely bounded homogeneous structures for the class $mathcalC$.

Recommendations

• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• 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
• On the reduction of the CSP dichotomy conjecture to digraphs
• Asking the Metaquestions in Constraint Tractability

Cites work

• A complexity dichotomy for poset constraint satisfaction
• A proof of the CSP dichotomy conjecture
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Affine systems of equations and counting infinitary logic
• An algebraic approach to multi-sorted constraints
• Automata theory in nominal sets
• Characterizations of several Maltsev conditions.
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Constraint Satisfaction Problems of Bounded Width
• Constraint satisfaction problems over the integers with successor
• Constraints, MMSNP and expander relational structures
• Cores of Countably Categorical Structures
• Datalog and constraint satisfaction with infinite templates
• Decidability of definability
• Equivalence constraint satisfaction problems
• Existence theorems for weakly symmetric operations
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 1149443 (Why is no real title available?)
• scientific article; zbMATH DE number 3019695 (Why is no real title available?)
• Locally finite constraint satisfaction problems
• On free actions, minimal flows, and a problem by Ellis
• Point algebras for temporal reasoning: Algorithms and complexity
• Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk).
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• The complexity of equality constraint languages
• The complexity of phylogeny constraint satisfaction
• 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 wonderland of reflections
• Topological Birkhoff
• Turing machines with atoms
• Turing machines with atoms, constraint satisfaction problems, and descriptive complexity

Cited in

(21)

• Dichotomies for classes of homomorphism problems involving unary functions
• Permutation groups with small orbit growth
• Using model theory to find decidable and tractable description logics with concrete domains
• General lower bounds and improved algorithms for infinite-domain CSPs
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• PROJECTIVE CLONE HOMOMORPHISMS
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's
• Complexity classification transfer for CSPs via algebraic products
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• Canonical polymorphisms of Ramsey structures and the unique interpolation property
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• Forbidden tournaments and the orientation completion problem
• Network satisfaction problems solved by k-consistency
• An order out of nowhere: a new algorithm for infinite-domain CSPs
• The complexity of resilience problems via valued constraint satisfaction problems
• Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
• A complexity dichotomy in spatial reasoning via Ramsey theory
• Generalized completion problems with forbidden tournaments
• Smooth approximations and relational width collapses
• The complexity of resilience problems via valued constraint satisfaction

This page was built for publication: A dichotomy for first-order reducts of unary structures

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