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

DOI10.1137/20M1383471zbMATH Open1483.68141OpenAlexW3006207249MaRDI QIDQ5067445FDOQ5067445

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

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?)
• Title not available (Why is that?)
• A complexity dichotomy for poset constraint satisfaction
• A proof of the CSP dichotomy conjecture
• A relationship between difference hierarchies and relativized polynomial hierarchies
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• A survey of homogeneous structures
• A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity hierarchies beyond elementary
• Complexity of infinite-domain constraint satisfaction
• Constraint satisfaction problems for reducts of homogeneous graphs
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• Existence theorems for weakly symmetric operations
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• Finitely related algebras in congruence modular varieties have few subpowers
• Homogenizable relational structures
• Monotone monadic SNP and constraint satisfaction
• Non-dichotomies in Constraint Satisfaction Complexity
• On the Structure of Polynomial Time Reducibility
• PROJECTIVE CLONE HOMOMORPHISMS
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• The complexity of temporal constraint satisfaction problems
• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• The wonderland of reflections
• Topological Birkhoff
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• Uniform Birkhoff
• Universal graphs with forbidden subgraphs and algebraic closure
• Universial structures with forbidden homomorphisms
• \( \omega \)-categorical structures avoiding height 1 identities

Cited In (7)

• On the descriptive complexity of temporal constraint satisfaction problems
• Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems
• \( \omega \)-categorical structures avoiding height 1 identities
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• 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)