Monotone monadic SNP and constraint satisfaction

DOI10.1145/167088.167245zbMath1310.68086MaRDI QIDQ5248532

Moshe Y. Vardi, Tomás Feder

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

Mathematics Subject Classification ID

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, Constraint satisfaction and semilinear expansions of addition over the rationals and the reals, 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, Boolean dependence logic and partially-ordered connectives, 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