Monotone monadic SNP and constraint satisfaction
From MaRDI portal
Publication:5248532
DOI10.1145/167088.167245zbMath1310.68086OpenAlexW1970318994MaRDI QIDQ5248532
Publication date: 7 May 2015
Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/167088.167245
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Constraint satisfaction and semilinear expansions of addition over the rationals and the reals, Boolean dependence logic and partially-ordered connectives, When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems, Unnamed Item, Unnamed Item, Complexity of tree homomorphisms, List homomorphisms to reflexive graphs, Complexity of \(C_k\)-coloring in hereditary classes of graphs, The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial, The algebraic structure of the densification and the sparsification tasks for CSPs, Semidefinite programming and its applications to NP problems, The 2CNF Boolean formula satisfiability problem and the linear space hypothesis, List homomorphisms to separable signed graphs, Min orderings and list homomorphism dichotomies for signed and unsigned graphs, Constraint satisfaction problem: what makes the problem easy, Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments, Computing a partition function of a generalized pattern-based energy over a semiring, Backdoor Sets for CSP., On the CSP Dichotomy Conjecture, Locally Injective Homomorphism to the Simple Weight Graphs, Constraint Satisfaction Parameterized by Solution Size, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Unnamed Item, Constraint satisfaction problems over semilattice block Mal'tsev algebras, Unnamed Item, Computational complexity relationship between compaction, vertex-compaction, and retraction, A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP, A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties, Constraints, consistency and closure, On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets, Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon, A Logical Approach to Constraint Satisfaction, A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results, Conjunctive-query containment and constraint satisfaction, Complexity of homomorphisms to direct products of graphs, List homomorphism problems for signed trees
