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 AsGet 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
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.
Keywords
- Constraint satisfaction
- complexity
- succinct representations
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads