When symmetries are not enough: a hierarchy of hard constraint satisfaction problems

DOI10.1137/20M1383471zbMATH Open1483.68141arXiv2002.07054OpenAlexW3006207249MaRDI QIDQ5067445FDOQ5067445

Antoine Mottet, Michael Pinsker, J. Jonušas, Pierre Gillibert, Michael Kompatscher

Publication date: 1 April 2022

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

Abstract: We produce a class of $omega$-categorical structures with finite signature by applying a model-theoretic construction -- a refinement of the Hrushosvki-encoding -- to $omega$-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate $omega$-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity, and $omega$-categorical templates that show that membership in any given complexity class cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of $omega$-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.

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

Recommendations

• Non-dichotomies in Constraint Satisfaction Complexity
• Complexity of infinite-domain constraint satisfaction
• \( \omega \)-categorical structures avoiding height 1 identities
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• Universal algebra and hardness results for constraint satisfaction problems

zbMATH Keywords

topologyconstraint satisfaction problempolymorphismsinfinite domain\(\omega\)-categoricitynondichotomy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Equational classes, universal algebra in model theory (03C05) Categoricity and completeness of theories (03C35) Operations and polynomials in algebraic structures, primal algebras (08A40) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Cites Work

• Title not available (Why is that?)
• Existence theorems for weakly symmetric operations
• Schaefer's theorem for graphs
• Non-dichotomies in Constraint Satisfaction Complexity
• The complexity of temporal constraint satisfaction problems
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
• Monotone monadic SNP and constraint satisfaction
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Complexity hierarchies beyond elementary
• Universal graphs with forbidden subgraphs and algebraic closure
• A survey of homogeneous structures
• Topological Birkhoff
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Homogenizable relational structures
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
• A relationship between difference hierarchies and relativized polynomial hierarchies
• PROJECTIVE CLONE HOMOMORPHISMS
• Complexity of Infinite-Domain Constraint Satisfaction
• Uniform Birkhoff
• Finitely related algebras in congruence modular varieties have few subpowers
• The wonderland of reflections
• Title not available (Why is that?)
• A complexity dichotomy for poset constraint satisfaction
• A Proof of the CSP Dichotomy Conjecture
• Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
• Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• Universal Structures with Forbidden Homomorphisms
• Title not available (Why is that?)
• 𝜔-categorical structures avoiding height 1 identities

Cited In (5)

• On the descriptive complexity of temporal constraint satisfaction problems
• Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• Non-dichotomies in Constraint Satisfaction Complexity
• Reducing symmetries to generate easier SAT instances

This page was built for publication: When symmetries are not enough: a hierarchy of hard constraint satisfaction problems

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