The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
From MaRDI portal
Publication:4210136
DOI10.1137/S0097539794266766zbMath0914.68075OpenAlexW2150339067WikidataQ56389117 ScholiaQ56389117MaRDI QIDQ4210136
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
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Discrete mathematics in relation to computer science (68R99)
Related Items
Constraint satisfaction and semilinear expansions of addition over the rationals and the reals, Tractability in constraint satisfaction problems: a survey, In praise of homomorphisms, Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies, Hard constraint satisfaction problems have hard gaps at location 1, The complexity of weighted Boolean \#CSP with mixed signs, Binary constraint satisfaction problems defined by excluded topological minors, The complexity of constraint satisfaction games and QCSP, Tropically convex constraint satisfaction, Some complete and intermediate polynomials in algebraic complexity theory, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Colourings, homomorphisms, and partitions of transitive digraphs, Axiomatisability and hardness for universal Horn classes of hypergraphs, Digraph matrix partitions and trigraph homomorphisms, Equivariant algorithms for constraint satisfaction problems over coset templates, Testing list \(H\)-homomorphisms, The structure of bi-arc trees, A complexity dichotomy for signed \(\mathbf{H}\)-colouring, View-based query processing: on the relationship between rewriting, answering and losslessness, Constraint satisfaction, irredundant axiomatisability and continuous colouring, Towards a characterization of constant-factor approximable finite-valued CSPs, Dualities and dual pairs in Heyting algebras, Towards a dichotomy theorem for the counting constraint satisfaction problem, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights, Obstructions to partitions of chordal graphs, Relativised homomorphism preservation at the finite level, List-homomorphism problems on graphs and arc consistency, A strong Mal'cev condition for locally finite varieties omitting the unary type, Reconfiguration in bounded bandwidth and tree-depth, On the complexity of \(\mathbb{H}\)-coloring for special oriented trees, On tree-preserving constraints, Conservative constraint satisfaction re-revisited, A new line of attack on the dichotomy conjecture, Computational complexity of covering three-vertex multigraphs, Enumerating homomorphisms, Maltsev digraphs have a majority polymorphism, The power of propagation: when GAC is enough, Computing hypergraph width measures exactly, Reflexive digraphs with near unanimity polymorphisms, The complexity of surjective homomorphism problems-a survey, The wonderland of reflections, Hybrid tractability of valued constraint problems, Interleaved adjoints of directed graphs, Locally constrained graph homomorphisms -- structure, complexity, and applications, Colouring, constraint satisfaction, and complexity, Learnability of quantified formulas., Computational complexity of auditing finite attributes in statistical databases, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, On the restricted homomorphism problem, Regular families of forests, antichains and duality pairs of relational structures, The complexity of counting quantifiers on equality languages, Tractability conditions for numeric CSPs, 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, Gap theorems for robust satisfiability: Boolean CSPs and beyond, List H-coloring a graph by removing few vertices, The complexity of the list homomorphism problem for graphs, \(2K_{2}\) vertex-set partition into nonempty parts, The Helly property and satisfiability of Boolean formulas defined on set families, Tractable structures for constraint satisfaction with truth tables, On solvability of systems of polynomial equations, Absolute retracts and varieties generated by chordal graphs, An approximation trichotomy for Boolean \#CSP, Disjunction property and complexity of substructural logics, Recognizing frozen variables in constraint satisfaction problems, The complexity of counting homomorphisms seen from the other side, There are no pure relational width 2 constraint satisfaction problems, Computing vertex-surjective homomorphisms to partially reflexive trees, CSP duality and trees of bounded pathwidth, A polynomial relational class of binary CSP, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, The complexity of list edge-partitions for simple graphs, Backdoors into heterogeneous classes of SAT and CSP, Connected obstructions to full graph homomorphisms, \(H\)-coloring degree-bounded (acyclic) digraphs, Existentially restricted quantified constraint satisfaction, Universal algebra and hardness results for constraint satisfaction problems, Affine systems of equations and counting infinitary logic, Maximal infinite-valued constraint languages, The complexity of satisfiability problems: Refining Schaefer's theorem, Minimization of locally defined submodular functions by optimal soft arc consistency, Relatively quantified constraint satisfaction, Partially ordered connectives and monadic monotone strict NP, The SAT-UNSAT transition for random constraint satisfaction problems, Extension problems with degree bounds, Determining the consistency of partial tree descriptions, Complexity of planar signed graph homomorphisms to cycles, A combinatorial constraint satisfaction problem dichotomy classification conjecture, Homomorphisms of sparse signed graphs, Peek arc consistency, A surprising permanence of old motivations (a not-so-rigid story), Edge-switching homomorphisms of edge-coloured graphs, Congruence modularity implies cyclic terms for finite algebras, Conjunctive-query containment and constraint satisfaction, Distance constraint satisfaction problems, A dichotomy for real weighted Holant problems, Periodic constraint satisfaction problems: Tractable subclasses, \(H\)-coloring dichotomy revisited, Quantified Constraint Satisfaction Problem on Semicomplete Digraphs, The Complexity of General-Valued CSPs, Small Promise CSPs that reduce to large CSPs, Constraint Satisfaction Problems over the Integers with Successor, On Planar Boolean CSP, Lower Bounds for the Graph Homomorphism Problem, A Galois Connection for Valued Constraint Languages of Infinite Size, Algebraic Properties of Valued Constraint Satisfaction Problem, Sherali-Adams Relaxations for Valued CSPs, Complexity and polymorphisms for digraph constraint problems under some basic constructions, Unnamed Item, Necessary Conditions for Tractability of Valued CSPs, When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems, Constraint Satisfaction Problems Solvable by Local Consistency Methods, Satisfiability in MultiValued Circuits, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, The Power of Sherali--Adams Relaxations for General-Valued CSPs, Unnamed Item, Unnamed Item, NP for Combinatorialists, First-Order Model Checking Problems Parameterized by the Model, Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs, Unnamed Item, The Complexity of Boolean Surjective General-Valued CSPs, Unnamed Item, Unnamed Item, Unnamed Item, Non-dichotomies in Constraint Satisfaction Complexity, Binarisation for Valued Constraint Satisfaction Problems, Proof Complexity Meets Algebra, Unnamed Item, The Complexity of Valued CSPs, Backdoor Sets for CSP., Constraint Satisfaction Problems over Numeric Domains, SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS, Quantified Constraints in Twenty Seventeen, The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems, Bounded Tree-Width and CSP-Related Problems, Minimum Violation Vertex Maps and Their Applications to Cut Problems, Algebra and the Complexity of Digraph CSPs: a Survey, On the Complexity of Holant Problems, Counting Constraint Satisfaction Problems., 𝜔-categorical structures avoiding height 1 identities, Varieties with few subalgebras of powers, Model checking existential logic on partially ordered sets, A Generalized Version of the Baker–Pixley Theorem, Solving equation systems in ω-categorical algebras, Tractability of quantified temporal constraints to the max, Finding Reductions Automatically, Weak classification of finite groups, Unnamed Item, Constraint Satisfaction with Counting Quantifiers, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the Computational Complexity of Monotone Constraint Satisfaction Problems, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP, Smooth digraphs modulo primitive positive constructability and cyclic loop conditions, Loop conditions for strongly connected digraphs, Unnamed Item, THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM, Homomorphism Reconfiguration via Homotopy, Unnamed Item, Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures, Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems), Unnamed Item, Adventures in monotone complexity and TFNP, Dismantlability, Connectedness, and Mixing in Relational Structures, Testing the Complexity of a Valued CSP Language, A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties, CSP dichotomy for special triads, Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction, Tree-Width for First Order Formulae, Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems, OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT, TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS, The existence of a near-unanimity term in a finite algebra is decidable, Constraint Satisfaction Problems for Reducts of Homogeneous Graphs, Unnamed Item, Palindromes in finite groups and the Explorer-Director game, Topological Birkhoff, Time Complexity of Constraint Satisfaction via Universal Algebra, Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices, A Dichotomy for First-Order Reducts of Unary Structures, Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon, The Complexity of Quantified Constraints Using the Algebraic Formulation, Twisted Automorphisms and Twisted Right Gyrogroups, Unnamed Item, Recent Results on the Algebraic Approach to the CSP, Dualities for Constraint Satisfaction Problems, A Logical Approach to Constraint Satisfaction, The Power of Linear Programming for General-Valued CSPs, Solving CSPs Using Weak Local Consistency, Matrix Partitions with Finitely Many Obstructions, Homomorphisms of Signed Graphs, Unnamed Item, Unnamed Item, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, CLAP: A New Algorithm for Promise CSPs, Topology and Adjunction in Promise Constraint Satisfaction, Unnamed Item, Unnamed Item, The smallest hard trees, \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's, Constraint satisfaction problem: what makes the problem easy, On guarded extensions of MMSNP, Monoidal Width: Capturing Rank Width, Surjective polymorphisms of directed reflexive cycles, Unnamed Item, Unnamed Item, Max-Closed Semilinear Constraint Satisfaction, Fanout limitations on constraint systems, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, Computational complexity relationship between compaction, vertex-compaction, and retraction, Generalized satisfiability problems via operator assignments, Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems, The Complexity of Symmetric Boolean Parity Holant Problems, Uniform Constraint Satisfaction Problems and Database Theory, Constraint Satisfaction Problems with Infinite Templates, Introduction to the Maximum Solution Problem, Unnamed Item, Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations, Dichotomies for classes of homomorphism problems involving unary functions, Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity, The complexity of minimal satisfiability problems, The complexity of signed graph and edge-coloured graph homomorphisms, On the Complexity of the Model Checking Problem, A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\), Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, A tetrachotomy of ontology-mediated queries with a covering axiom, Semantic Acyclicity on Graph Databases, Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, The Complexity of Counting Quantifiers on Equality Languages, What makes propositional abduction tractable, On planar valued CSPs, On the speed of constraint propagation and the time complexity of arc consistency testing, The connectivity of Boolean satisfiability: dichotomies for formulas and circuits, The Complexity of Approximately Counting Tree Homomorphisms, Counting List Matrix Partitions of Graphs, Correspondence homomorphisms to reflexive graphs, Emptiness problems for distributed automata, Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering?, Is Polynomial Time Choiceless?, The dynamic complexity of acyclic hypergraph homomorphisms, Complexity of correspondence \(H\)-colourings, The complexity of approximating bounded-degree Boolean \(\#\)CSP, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, On digraph coloring problems and treewidth duality, Majority constraints have bounded pathwidth duality, Generalised dualities and maximal finite antichains in the homomorphism order of relational structures, Forbidden lifts (NP and CSP for combinatorialists), Majority functions on structures with finite duality, Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022, Many Facets of Dualities, Constraints, MMSNP and expander relational structures, On finitely related semigroups., Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs, Semilattice polymorphisms and chordal graphs, Constraint satisfaction with succinctly specified relations, A structured view on weighted counting with relations to counting, quantum computation and applications, The existence of a near-unanimity function is decidable, Dismantlability, connectedness, and mixing in relational structures, The complexity of soft constraint satisfaction, The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems, On rainbow-free colourings of uniform hypergraphs, Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees, On the CSP Dichotomy Conjecture, Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms, Reflexive graphs with near unanimity but no semilattice polymorphisms, Counting truth assignments of formulas of bounded tree-width or clique-width, A combinatorial characterization of resolution width, On twisted subgroups and Bol loops of odd order., Complexity of clausal constraints over chains, Retractions onto series-parallel posets, A discrete homotopy theory for binary reflexive structures, Unnamed Item, Surjective \(H\)-colouring: new hardness results, The complexity of tropical graph homomorphisms, Minimum cost and list homomorphisms to semicomplete digraphs, Combinatorial problems raised from 2-semilattices, A new tractable class of constraint satisfaction problems, Constraint satisfaction problems over semilattice block Mal'tsev algebras, Dichotomy for tree-structured trigraph list homomorphism problems, The \(C_{k}\)-extended graft construction, Building blocks for the variety of absolute retracts, THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA, Parameterized counting of partially injective homomorphisms, Reconfiguration of homomorphisms to reflexive digraph cycles, Graph partitions with prescribed patterns, Obstructions to locally injective oriented improper colourings, RESIDUAL PROPERTIES OF SIMPLE GRAPHS, Decidability of absorption in relational structures of bounded width., TERM EQUATION SATISFIABILITY OVER FINITE ALGEBRAS, From \(A\) to \(B\) to \(Z\), Permutation groups with small orbit growth, Join colourings of chordal graphs, Dichotomy for finite tournaments of mixed-type, Galois connections for patterns: an algebra of labelled graphs, Robustly Solvable Constraint Satisfaction Problems, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Minimum Cost Homomorphisms with Constrained Costs, Tractable combinations of theories via sampling, On algebras with many symmetric operations, Adjusted Interval Digraphs, The number of clones determined by disjunctions of unary relations, A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights, The recognition of bound quivers using edge-coloured homomorphisms, Quasi-Transitive Digraphs and Their Extensions, CSP DICHOTOMY FOR SPECIAL POLYADS, COMPUTATIONAL COMPLEXITY OF VARIOUS MAL'CEV CONDITIONS, Polyadic sets and homomorphism counting, A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results, Uniform and nonuniform recognizability., The complexity of partition functions, Constructing NP-intermediate problems by blowing holes with parameters of various properties, Logical compactness and constraint satisfaction problems, Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}), ASNP: a tame fragment of existential second-order logic, Commutative idempotent groupoids and the constraint satisfaction problem., Strong near subgroups and left gyrogroups, Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem, High girth hypergraphs with unavoidable monochromatic or rainbow edges
Uses Software
