The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

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

zbMATH Keywords

graph coloringgroup theorylinear equationssatisfiabilityDatalog

Mathematics Subject Classification ID

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)

• In praise of homomorphisms
• 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
• A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
• 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
• 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
• 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
• Title not available (Why is that?)
• 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
• Tractability of quantified temporal constraints to the max
• CSP dichotomy for special polyads
• 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
• The structure of bi-arc trees
• Algebraic properties of valued constraint satisfaction problem
• Binary constraint satisfaction problems defined by excluded topological minors
• 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

Uses Software

• Datalog

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)