On the CSP Dichotomy Conjecture
From MaRDI portal
Publication:3007637
DOI10.1007/978-3-642-20712-9_26zbMath1332.68065MaRDI QIDQ3007637
Publication date: 17 June 2011
Published in: Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_26
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of H-coloring
- Constraints, consistency and closure
- Constraints, MMSNP and expander relational structures
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- NP by Means of Lifts and Shadows
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Undirected ST-connectivity in log-space
- ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
- The structure of finite algebras
- On the Structure of Polynomial Time Reducibility
- Synthesizing constraint expressions
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Constraint Satisfaction Problems of Bounded Width
- Monotone monadic SNP and constraint satisfaction
- Generalized Majority-Minority Operations are Tractable
- Classifying the Complexity of Constraints Using Finite Algebras
- Tractability and Learnability Arising from Algebras with Few Subpowers
- The complexity of satisfiability problems
- Universal Algebra and Hardness Results for Constraint Satisfaction Problems
- Affine Systems of Equations and Counting Infinitary Logic
- Constraint Satisfaction, Logic and Forbidden Patterns
- A Simple Algorithm for Mal'tsev Constraints
- Recent Results on the Algebraic Approach to the CSP
- Dualities for Constraint Satisfaction Problems
