Constraint Satisfaction with Succinctly Specified Relations
Hubie Chen, Martin Grohe · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2006
The general intractability of the constraint satisfaction problem has motivated the study of the complexity of restricted cases of this problem. Thus far, the literature has primarily considered the formulation of the CSP where constraint relations are given explicitly. We initiate the systematic study of CSP complexity with succinctly specified constraint relations. This is joint work with Hubie Chen.