The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
From MaRDI portal
Publication:4210136
DOI10.1137/S0097539794266766zbMATH Open0914.68075OpenAlexW2150339067WikidataQ56389117 ScholiaQ56389117MaRDI QIDQ4210136FDOQ4210136
Authors: Moshe Y. Vardi, Tomás Feder 
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539794266766
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
Discrete mathematics in relation to computer science (68R99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (only showing first 100 items - show all)
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- Proof Complexity Meets Algebra
- Uniform and nonuniform recognizability.
- CSP dichotomy for special polyads
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- Join colourings of chordal graphs
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- Dismantlability, connectedness, and mixing in relational structures
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- High girth hypergraphs with unavoidable monochromatic or rainbow edges
- The quantum monad on relational structures
- Quasi-transitive digraphs and their extensions
- On the Complexity of Holant Problems
- Semilattice polymorphisms and chordal graphs
- Surjective \(H\)-colouring: new hardness results
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- Homomorphism reconfiguration via homotopy
- \(n\)-permutability and linear Datalog implies symmetric Datalog
- Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- Computational complexity of various Mal'cev conditions
- A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
- Parameterized counting of partially injective homomorphisms
- Why is it hard to obtain a dichotomy for consistent query answering?
- A dichotomy for first-order reducts of unary structures
- From \(A\) to \(B\) to \(Z\)
- Permutation groups with small orbit growth
- Binarisation for valued constraint satisfaction problems
- A tetrachotomy of ontology-mediated queries with a covering axiom
- Counting List Matrix Partitions of Graphs
- Galois connections for patterns: an algebra of labelled graphs
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
- Dichotomy for tree-structured trigraph list homomorphism problems
- Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
- The Complexity of Counting Quantifiers on Equality Languages
- Tractable combinations of theories via sampling
- Quantified constraint satisfaction problem on semicomplete digraphs
- NP for Combinatorialists
- On tree-preserving constraints
- The wonderland of reflections
- Emptiness problems for distributed automata
- First-Order Model Checking Problems Parameterized by the Model
- Absorption in universal algebra and CSP
- Algebra and the complexity of digraph CSPs: a survey
- The complexity of quantified constraints using the algebraic formulation
- Correspondence homomorphisms to reflexive graphs
- On the CSP Dichotomy Conjecture
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- A structured view on weighted counting with relations to counting, quantum computation and applications
- Commutative idempotent groupoids and the constraint satisfaction problem.
- Constraint satisfaction problems for reducts of homogeneous graphs
- On rainbow-free colourings of uniform hypergraphs
- Polyadic sets and homomorphism counting
- ASNP: a tame fragment of existential second-order logic
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- Reasoning on property graphs with graph generating dependencies
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- Smooth digraphs modulo primitive positive constructability and cyclic loop conditions
- Dismantlability, Connectedness, and Mixing in Relational Structures
- Generalisations of matrix partitions: complexity and obstructions
- 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
- Title not available (Why is that?)
- Functors on relational structures which admit both left and right adjoints
- Tree-Width for First Order Formulae
- On guarded extensions of MMSNP
- Monoidal Width: Capturing Rank Width
- Generalized satisfiability problems via operator assignments
- Quantified Constraints in Twenty Seventeen
- Gyro-groups, gyro-splittings and co-homology
- Constraint reasoning
- Consistency for counting quantifiers
- CLAP: A New Algorithm for Promise CSPs
- Topology and Adjunction in Promise Constraint Satisfaction
- Testing the Complexity of a Valued CSP Language
- Surjective polymorphisms of directed reflexive cycles
- Constraint satisfaction, graph isomorphism, and the pebbling comonad
- \( \omega \)-categorical structures avoiding height 1 identities
- Counting constraint satisfaction problems
- The smallest hard trees
- Complexity classification transfer for CSPs via algebraic products
- Computational complexity relationship between compaction, vertex-compaction, and retraction
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Small Promise CSPs that reduce to large CSPs
- Towards a dichotomy for the list switch homomorphism problem for signed graphs
- Palindromes in finite groups and the explorer-director game
- Title not available (Why is that?)
- Finite algebras with Hom-sets of polynomial size
- Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
- Approximate graph colouring and the hollow shadow
- The language of stratified sets is confluent and strongly normalising
- Quantaloidal approach to constraint satisfaction
- Hybrid VCSPs with crisp and valued conservative templates
Uses Software
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)
