The complexity of maximal constraint languages

DOI10.1145/380752.380868zbMath1323.68294MaRDI QIDQ5176025

Andrei A. Krokhin, Andrei A. Bulatov, Peter G. Jeavons

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380868

zbMATH Keywords

complexity; NP-completeness; relational clone; tractability; constraint language; algebraic invariance property; constraint satisfaciton problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Basics of Galois Connections, Introduction to the Maximum Solution Problem, Tractable structures for constraint satisfaction with truth tables, Recognizing frozen variables in constraint satisfaction problems, Periodic constraint satisfaction problems: Tractable subclasses, Existentially restricted quantified constraint satisfaction, Maximal infinite-valued constraint languages, The complexity of soft constraint satisfaction, Combinatorial problems raised from 2-semilattices