The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
From MaRDI portal
Publication:4210136
Recommendations
- A Dichotomy Theorem for Typed Constraint Satisfaction Problems
- On the Computational Complexity of Monotone Constraint Satisfaction Problems
- scientific article; zbMATH DE number 1670830
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- A proof of the CSP dichotomy conjecture
Cited in
(only showing first 100 items - show all)- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- List-homomorphism problems on graphs and arc consistency
- A Generalized Version of the Baker–Pixley Theorem
- In praise of homomorphisms
- Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
- The number of clones determined by disjunctions of unary relations
- Uniform and nonuniform recognizability.
- Surjective \texttt{H}-colouring over reflexive digraphs
- Proof Complexity Meets Algebra
- Reasoning on property graphs with graph generating dependencies
- The complexity of minimal satisfiability problems
- Tractability conditions for numeric CSPs
- Tractability of quantified temporal constraints to the max
- CSP dichotomy for special polyads
- scientific article; zbMATH DE number 7561550 (Why is no real title available?)
- A dichotomy for real weighted Holant problems
- Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems
- Many Facets of Dualities
- On finitely related semigroups.
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- Residual properties of simple graphs
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
- Learnability of quantified formulas.
- Graph partitions with prescribed patterns
- Dismantlability, Connectedness, and Mixing in Relational Structures
- A Logical Approach to Constraint Satisfaction
- Join colourings of chordal graphs
- The complexity of surjective homomorphism problems-a survey
- CSP dichotomy for special triads
- The Helly property and satisfiability of Boolean formulas defined on set families
- Absolute retracts and varieties generated by chordal graphs
- A discrete homotopy theory for binary reflexive structures
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- Generalisations of matrix partitions: complexity and obstructions
- SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Dismantlability, connectedness, and mixing in relational structures
- Conditional dichotomy of Boolean ordered promise CSPs
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- On the descriptive complexity of temporal constraint satisfaction problems
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Tractability in constraint satisfaction problems: a survey
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- scientific article; zbMATH DE number 7378350 (Why is no real title available?)
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Recent Results on the Algebraic Approach to the CSP
- Is polynomial time choiceless?
- scientific article; zbMATH DE number 7536562 (Why is no real title available?)
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- Enumerating homomorphisms
- Tree-Width for First Order Formulae
- Functors on relational structures which admit both left and right adjoints
- Colouring, constraint satisfaction, and complexity
- High girth hypergraphs with unavoidable monochromatic or rainbow edges
- There are no pure relational width 2 constraint satisfaction problems
- Recognizing frozen variables in constraint satisfaction problems
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- The complexity of satisfiability problems: Refining Schaefer's theorem
- On guarded extensions of MMSNP
- Monoidal Width: Capturing Rank Width
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- The complexity of weighted Boolean \#CSP with mixed signs
- The power of linear programming for general-valued CSPs
- Tractable structures for constraint satisfaction with truth tables
- Disjunction property and complexity of substructural logics
- Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
- The quantum monad on relational structures
- Time complexity of constraint satisfaction via universal algebra
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Quasi-transitive digraphs and their extensions
- Semilattice polymorphisms and chordal graphs
- TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Dualities for Constraint Satisfaction Problems
- On the Complexity of Holant Problems
- Hybrid tractability of valued constraint problems
- Uniform Constraint Satisfaction Problems and Database Theory
- Constraint satisfaction with counting quantifiers
- Dichotomy for finite tournaments of mixed-type
- Surjective \(H\)-colouring: new hardness results
- scientific article; zbMATH DE number 7561584 (Why is no real title available?)
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- The complexity of counting homomorphisms seen from the other side
- Generalized satisfiability problems via operator assignments
- The complexity of conservative valued CSPs
- Backdoors into heterogeneous classes of SAT and CSP
- Introduction to the Maximum Solution Problem
- On twisted subgroups and Bol loops of odd order.
- A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
- Why are CSPs based on partition schemes computationally hard?
- View-based query processing: on the relationship between rewriting, answering and losslessness
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
- Conservative constraint satisfaction re-revisited
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- Computing hypergraph width measures exactly
- Maximal infinite-valued constraint languages
- Relatively quantified constraint satisfaction
This page was built for publication: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210136)
