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

DOI10.1137/20M1383471MaRDI QIDQ5067445zbMATHOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 7406819 (Why is no real title available?)
• 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)

• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems
• Non-dichotomies in Constraint Satisfaction Complexity
• \( \omega \)-categorical structures avoiding height 1 identities
• Reducing symmetries to generate easier SAT instances
• On the descriptive complexity of temporal constraint satisfaction problems
• Smooth approximations and CSPs over finitely bounded homogeneous structures

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)