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)
- 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
- Computational complexity of auditing finite attributes in statistical databases
- Complexity of correspondence \(H\)-colourings
- Model checking existential logic on partially ordered sets
- Robustly solvable constraint satisfaction problems
- On algebras with many symmetric operations
- Title not available (Why is that?)
- On the restricted homomorphism problem
- A Generalized Version of the Baker–Pixley Theorem
- 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
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)
