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)- CSP dichotomy for special triads
- The complexity of minimal satisfiability problems
- Edge-switching homomorphisms of edge-coloured graphs
- Dualities and dual pairs in Heyting algebras
- Lower bounds for the graph homomorphism problem
- Interleaved adjoints of directed graphs
- \(2K_{2}\) vertex-set partition into nonempty parts
- On solvability of systems of polynomial equations
- Solving equation systems in ω-categorical algebras
- Homomorphisms of signed graphs
- Constraint satisfaction with counting quantifiers
- Disjunction property and complexity of substructural logics
- Complexity of planar signed graph homomorphisms to cycles
- MAX-closed semilinear constraint satisfaction
- The power of linear programming for general-valued CSPs
- The SAT-UNSAT transition for random constraint satisfaction problems
- Minimization of locally defined submodular functions by optimal soft arc consistency
- In praise of homomorphisms
- Dichotomies for classes of homomorphism problems involving unary functions
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- Retractions onto series-parallel posets
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Congruence modularity implies cyclic terms for finite algebras
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Many Facets of Dualities
- Matrix Partitions with Finitely Many Obstructions
- Connected obstructions to full graph homomorphisms
- Periodic constraint satisfaction problems: Tractable subclasses
- \(H\)-coloring degree-bounded (acyclic) digraphs
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- The Complexity of Boolean Surjective General-Valued CSPs
- Minimum cost and list homomorphisms to semicomplete digraphs
- Tractability conditions for numeric CSPs
- Strong near subgroups and left gyrogroups
- A combinatorial characterization of resolution width
- CSP duality and trees of bounded pathwidth
- Semantic acyclicity on graph databases
- Adventures in monotone complexity and TFNP
- Learnability of quantified formulas.
- Existentially restricted quantified constraint satisfaction
- The complexity of symmetric Boolean parity Holant problems (extended abstract)
- Constraint Satisfaction Problems with Infinite Templates
- THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
- The complexity of list edge-partitions for simple graphs
- The complexity of tropical graph homomorphisms
- A polynomial relational class of binary CSP
- A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
- scientific article; zbMATH DE number 7376042 (Why is no real title available?)
- Constraints, MMSNP and expander relational structures
- A complexity dichotomy for signed \(\mathbf{H}\)-colouring
- Why are CSPs based on partition schemes computationally hard?
- On finitely related semigroups.
- The complexity of counting quantifiers on equality languages
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Recognizing frozen variables in constraint satisfaction problems
- Key (critical) relations preserved by a weak near-unanimity function
- Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms
- Rigid binary relations on a 4-element domain
- The complexity of signed graph and edge-coloured graph homomorphisms
- Gap theorems for robust satisfiability: Boolean CSPs and beyond
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
- On twisted subgroups and Bol loops of odd order.
- Fanout limitations on constraint systems
- The complexity of satisfiability problems: Refining Schaefer's theorem
- Forbidden lifts (NP and CSP for combinatorialists)
- SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Polyadic sets and homomorphism counting
- Correspondence homomorphisms to reflexive graphs
- \(n\)-permutability and linear Datalog implies symmetric Datalog
- First-Order Model Checking Problems Parameterized by the Model
- ASNP: a tame fragment of existential second-order logic
- A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
- A dichotomy for first-order reducts of unary structures
- Galois connections for patterns: an algebra of labelled graphs
- High girth hypergraphs with unavoidable monochromatic or rainbow edges
- Semilattice polymorphisms and chordal graphs
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
- From \(A\) to \(B\) to \(Z\)
- Permutation groups with small orbit growth
- Quantified constraint satisfaction problem on semicomplete digraphs
- Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
- Proof Complexity Meets Algebra
- NP for Combinatorialists
- Tractable combinations of theories via sampling
- Constraint satisfaction problems for reducts of homogeneous graphs
- A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
- The number of clones determined by disjunctions of unary relations
- Parameterized counting of partially injective homomorphisms
- Decidability of absorption in relational structures of bounded width.
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- A tetrachotomy of ontology-mediated queries with a covering axiom
- The quantum monad on relational structures
- Dichotomy for tree-structured trigraph list homomorphism problems
- On rainbow-free colourings of uniform hypergraphs
- Uniform and nonuniform recognizability.
- The complexity of quantified constraints using the algebraic formulation
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- Dismantlability, connectedness, and mixing in relational structures
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)
