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)
- The complexity of minimal satisfiability problems
- Many Facets of Dualities
- Tractability conditions for numeric CSPs
- On finitely related semigroups.
- Learnability of quantified formulas.
- SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- CSP dichotomy for special triads
- The power of linear programming for general-valued CSPs
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Recognizing frozen variables in constraint satisfaction problems
- The complexity of satisfiability problems: Refining Schaefer's theorem
- Constraint satisfaction with counting quantifiers
- Disjunction property and complexity of substructural logics
- Why are CSPs based on partition schemes computationally hard?
- On twisted subgroups and Bol loops of odd order.
- Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
- MAX-closed semilinear constraint satisfaction
- The complexity of tropical graph homomorphisms
- A polynomial relational class of binary CSP
- Matrix Partitions with Finitely Many Obstructions
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- Strong near subgroups and left gyrogroups
- THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
- The complexity of list edge-partitions for simple graphs
- Dualities and dual pairs in Heyting algebras
- The complexity of signed graph and edge-coloured graph homomorphisms
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Connected obstructions to full graph homomorphisms
- Fanout limitations on constraint systems
- Lower bounds for the graph homomorphism problem
- \(2K_{2}\) vertex-set partition into nonempty parts
- \(H\)-coloring degree-bounded (acyclic) digraphs
- A combinatorial characterization of resolution width
- The SAT-UNSAT transition for random constraint satisfaction problems
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- Congruence modularity implies cyclic terms for finite algebras
- The Complexity of Boolean Surjective General-Valued CSPs
- Semantic acyclicity on graph databases
- Complexity of planar signed graph homomorphisms to cycles
- Reconfiguration of homomorphisms to reflexive digraph cycles
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Existentially restricted quantified constraint satisfaction
- Edge-switching homomorphisms of edge-coloured graphs
- Interleaved adjoints of directed graphs
- Dichotomies for classes of homomorphism problems involving unary functions
- Adventures in monotone complexity and TFNP
- CSP duality and trees of bounded pathwidth
- Constraints, MMSNP and expander relational structures
- A complexity dichotomy for signed \(\mathbf{H}\)-colouring
- On solvability of systems of polynomial equations
- The complexity of symmetric Boolean parity Holant problems (extended abstract)
- Homomorphisms of signed graphs
- Constraint Satisfaction Problems with Infinite Templates
- The complexity of counting quantifiers on equality languages
- Forbidden lifts (NP and CSP for combinatorialists)
- Solving equation systems in ω-categorical algebras
- Retractions onto series-parallel posets
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Periodic constraint satisfaction problems: Tractable subclasses
- Minimum cost and list homomorphisms to semicomplete digraphs
- Minimization of locally defined submodular functions by optimal soft arc consistency
- 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
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- Gap theorems for robust satisfiability: Boolean CSPs and beyond
- List H-coloring a graph by removing few vertices
- 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
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)
