When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems
DOI10.1137/20M1383471zbMath1483.68141arXiv2002.07054OpenAlexW3006207249MaRDI QIDQ5067445
Antoine Mottet, Michael Pinsker, Pierre Gillibert, Michael Kompatscher, Julius 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
topologyconstraint satisfaction problempolymorphismsinfinite domain\(\omega\)-categoricitynondichotomy
Applications of universal algebra in computer science (08A70) Operations and polynomials in algebraic structures, primal algebras (08A40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Equational classes, universal algebra in model theory (03C05) Categoricity and completeness of theories (03C35) Computational aspects of satisfiability (68R07)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A strong Mal'cev condition for locally finite varieties omitting the unary type
- Homogenizable relational structures
- Existence theorems for weakly symmetric operations
- Universal graphs with forbidden subgraphs and algebraic closure
- Finitely related algebras in congruence modular varieties have few subpowers
- Uniform Birkhoff
- The wonderland of reflections
- A survey of homogeneous structures
- Schaefer's Theorem for Graphs
- Complexity Hierarchies beyond Elementary
- Complexity of Infinite-Domain Constraint Satisfaction
- 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
- The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
- A complexity dichotomy for poset constraint satisfaction
- Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
- Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures
- PROJECTIVE CLONE HOMOMORPHISMS
- A Proof of the CSP Dichotomy Conjecture
- 𝜔-categorical structures avoiding height 1 identities
- A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
- Universal Structures with Forbidden Homomorphisms
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
- Monotone monadic SNP and constraint satisfaction
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Classifying the Complexity of Constraints Using Finite Algebras
- Topological Birkhoff
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
This page was built for publication: When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems
