DagSemProc.06401.5.pdf
- Filesize: 229 kB
- 15 pages
Document
Constraint Satisfaction with Succinctly Specified Relations
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6401
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-15
Cite As Get BibTex
Hubie Chen and Martin Grohe. Constraint Satisfaction with Succinctly Specified Relations. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06401.5
Abstract
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.
Subject Classification
Keywords
- Constraint satisfaction
- complexity
- succinct representations
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads