The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
From MaRDI portal
(Redirected from 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)- Existentially restricted quantified constraint satisfaction
- Universal algebra and hardness results for constraint satisfaction problems
- Affine systems of equations and counting infinitary logic
- Maximal infinite-valued constraint languages
- The complexity of satisfiability problems: Refining Schaefer's theorem
- Minimization of locally defined submodular functions by optimal soft arc consistency
- Relatively quantified constraint satisfaction
- Partially ordered connectives and monadic monotone strict NP
- The SAT-UNSAT transition for random constraint satisfaction problems
- Extension problems with degree bounds
- Determining the consistency of partial tree descriptions
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- Peek arc consistency
- A surprising permanence of old motivations (a not-so-rigid story)
- Edge-switching homomorphisms of edge-coloured graphs
- Congruence modularity implies cyclic terms for finite algebras
- Learnability of quantified formulas.
- Conjunctive-query containment and constraint satisfaction
- Binary constraint satisfaction problems defined by excluded topological minors
- Tropically convex constraint satisfaction
- Axiomatisability and hardness for universal Horn classes of hypergraphs
- A complexity dichotomy for signed \(\mathbf{H}\)-colouring
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Relativised homomorphism preservation at the finite level
- Reconfiguration in bounded bandwidth and tree-depth
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- On tree-preserving constraints
- The power of propagation: when GAC is enough
- The wonderland of reflections
- A discrete homotopy theory for binary reflexive structures
- A new tractable class of constraint satisfaction problems
- Uniform and nonuniform recognizability.
- Strong near subgroups and left gyrogroups
- Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
- Dichotomies for classes of homomorphism problems involving unary functions
- The complexity of minimal satisfiability problems
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- On finitely related semigroups.
- Constraint satisfaction with succinctly specified relations
- On rainbow-free colourings of uniform hypergraphs
- Reflexive graphs with near unanimity but no semilattice polymorphisms
- Surjective \(H\)-colouring: new hardness results
- The complexity of tropical graph homomorphisms
- Parameterized counting of partially injective homomorphisms
- Reconfiguration of homomorphisms to reflexive digraph cycles
- From \(A\) to \(B\) to \(Z\)
- Permutation groups with small orbit growth
- Galois connections for patterns: an algebra of labelled graphs
- Tractable combinations of theories via sampling
- Polyadic sets and homomorphism counting
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- ASNP: a tame fragment of existential second-order logic
- High girth hypergraphs with unavoidable monochromatic or rainbow edges
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
- A tetrachotomy of ontology-mediated queries with a covering axiom
- Emptiness problems for distributed automata
- Complexity of correspondence \(H\)-colourings
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- A structured view on weighted counting with relations to counting, quantum computation and applications
- Dismantlability, connectedness, and mixing in relational structures
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- Dichotomy for tree-structured trigraph list homomorphism problems
- The \(C_{k}\)-extended graft construction
- The number of clones determined by disjunctions of unary relations
- A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- Commutative idempotent groupoids and the constraint satisfaction problem.
- The complexity of signed graph and edge-coloured graph homomorphisms
- What makes propositional abduction tractable
- On planar valued CSPs
- On the speed of constraint propagation and the time complexity of arc consistency testing
- The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
- Correspondence homomorphisms to reflexive graphs
- On digraph coloring problems and treewidth duality
- Majority constraints have bounded pathwidth duality
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- Forbidden lifts (NP and CSP for combinatorialists)
- Majority functions on structures with finite duality
- Constraints, MMSNP and expander relational structures
- Semilattice polymorphisms and chordal graphs
- The existence of a near-unanimity function is decidable
- The complexity of soft constraint satisfaction
- Counting truth assignments of formulas of bounded tree-width or clique-width
- A combinatorial characterization of resolution width
- On twisted subgroups and Bol loops of odd order.
- Complexity of clausal constraints over chains
- Retractions onto series-parallel posets
- Minimum cost and list homomorphisms to semicomplete digraphs
- Combinatorial problems raised from 2-semilattices
- Building blocks for the variety of absolute retracts
- Graph partitions with prescribed patterns
- Obstructions to locally injective oriented improper colourings
- Decidability of absorption in relational structures of bounded width.
- Join colourings of chordal graphs
- Dichotomy for finite tournaments of mixed-type
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)
