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
- In praise of homomorphisms
- Tractability of quantified temporal constraints to the max
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- A discrete homotopy theory for binary reflexive structures
- The Helly property and satisfiability of Boolean formulas defined on set families
- Absolute retracts and varieties generated by chordal graphs
- There are no pure relational width 2 constraint satisfaction problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dichotomy for finite tournaments of mixed-type
- A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
- The structure of bi-arc trees
- Algebraic properties of valued constraint satisfaction problem
- Binary constraint satisfaction problems defined by excluded topological minors
- Some complete and intermediate polynomials in algebraic complexity theory
- Tropically convex constraint satisfaction
- The power of Sherali-Adams relaxations for general-valued CSPs
- The power of propagation: when GAC is enough
- A finite-model-theoretic view on propositional proof complexity
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Reconfiguration in bounded bandwidth and tree-depth
- The \(C_{k}\)-extended graft construction
- Axiomatisability and hardness for universal Horn classes of hypergraphs
- Complexity of clausal constraints over chains
- Relativised homomorphism preservation at the finite level
- Building blocks for the variety of absolute retracts
- Determining the consistency of partial tree descriptions
- What makes propositional abduction tractable
- Partially ordered connectives and monadic monotone strict NP
- Extension problems with degree bounds
- A new line of attack on the dichotomy conjecture
- Computational complexity of covering three-vertex multigraphs
- A complete dichotomy rises from the capture of vanishing signatures
- A Galois connection for valued constraint languages of infinite size
- Towards a characterization of constant-factor approximable finite-valued CSPs
- The complexity of valued CSPs
- The recognition of bound quivers using edge-coloured homomorphisms
- A surprising permanence of old motivations (a not-so-rigid story)
- Peek arc consistency
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- Logical compactness and constraint satisfaction problems
- Learnability of solutions to conjunctive queries
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)
