A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP

DOI10.1137/19M128466XOpenAlexW3195027657WikidataQ123135727 ScholiaQ123135727MaRDI QIDQ4957913

Florent R. Madelaine, Antoine Mottet, Manuel Bodirsky

Publication date: 10 September 2021

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

Full work available at URL: https://doi.org/10.1137/19m128466x

zbMATH Keywords

constraint satisfaction problemspolymorphismsmonotone monadic SNP

Mathematics Subject Classification ID

Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(H\)-coloring dichotomy revisited
• Universal graphs with forbidden subgraphs and algebraic closure
• The wonderland of reflections
• Datalog and constraint satisfaction with infinite templates
• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• Constraints, MMSNP and expander relational structures
• Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
• A Model-Theoretic View on Qualitative Constraint Reasoning
• Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk).
• Constraint Satisfaction with Countable Homogeneous Templates
• Universal Structures and the logic of Forbidden Patterns
• 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
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• PROJECTIVE CLONE HOMOMORPHISMS
• 𝜔-categorical structures avoiding height 1 identities
• Universal Structures with Forbidden Homomorphisms
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• Monotone monadic SNP and constraint satisfaction
• Cores of Countably Categorical Structures
• Classifying the Complexity of Constraints Using Finite Algebras
• A Characterisation of First-Order Constraint Satisfaction Problems
• Constraint Satisfaction, Logic and Forbidden Patterns
• On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems