Monotone monadic SNP and constraint satisfaction
From MaRDI portal
Publication:5248532
DOI10.1145/167088.167245zbMath1310.68086MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
A Logical Approach to Constraint Satisfaction, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, List homomorphisms to reflexive graphs, Constraints, consistency and closure, Conjunctive-query containment and constraint satisfaction, Complexity of homomorphisms to direct products of graphs, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Complexity of tree homomorphisms, A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results, Unnamed Item, On the CSP Dichotomy Conjecture, Locally Injective Homomorphism to the Simple Weight Graphs, Constraint Satisfaction Parameterized by Solution Size
