Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings |
| Seiten | 748-757 |
| Seitenumfang | 10 |
| Publikationsstatus | Veröffentlicht - 2007 |
| Veranstaltung | 3rd Conference on Computability in Europe, CiE 2007 - Siena, Italien Dauer: 18 Juni 2007 → 23 Juni 2007 |
Publikationsreihe
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Band | 4497 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (elektronisch) | 1611-3349 |
Abstract
The input to a constraint satisfaction problem (CSP) consists of a set of variables, each with a domain, and constraints between these variables formulated by relations over the appropriate domains; the question is if there is an assignment of values to the variables that satisfies all constraints. Different algorithmic tasks for CSPs (checking satisfiability, counting the number of solutions, enumerating all solutions) can be used to model many problems in areas such as computational logic, artificial intelligence, circuit design, etc. We will survey results on the complexity of these computational tasks as a function of properties of the allowed constraint relations. Particular attention is paid to the special case of Boolean constraint relations.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Informatik (insg.)
- Allgemeine Computerwissenschaft
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings. 2007. S. 748-757 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 4497 LNCS).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - Computational complexity of constraint satisfaction
AU - Vollmer, Heribert
PY - 2007
Y1 - 2007
N2 - The input to a constraint satisfaction problem (CSP) consists of a set of variables, each with a domain, and constraints between these variables formulated by relations over the appropriate domains; the question is if there is an assignment of values to the variables that satisfies all constraints. Different algorithmic tasks for CSPs (checking satisfiability, counting the number of solutions, enumerating all solutions) can be used to model many problems in areas such as computational logic, artificial intelligence, circuit design, etc. We will survey results on the complexity of these computational tasks as a function of properties of the allowed constraint relations. Particular attention is paid to the special case of Boolean constraint relations.
AB - The input to a constraint satisfaction problem (CSP) consists of a set of variables, each with a domain, and constraints between these variables formulated by relations over the appropriate domains; the question is if there is an assignment of values to the variables that satisfies all constraints. Different algorithmic tasks for CSPs (checking satisfiability, counting the number of solutions, enumerating all solutions) can be used to model many problems in areas such as computational logic, artificial intelligence, circuit design, etc. We will survey results on the complexity of these computational tasks as a function of properties of the allowed constraint relations. Particular attention is paid to the special case of Boolean constraint relations.
KW - Clone
KW - Computational complexity
KW - Constraint satisfaction
KW - Galois connection
KW - Polymorphism
KW - Satisfiability problems
UR - http://www.scopus.com/inward/record.url?scp=38149018390&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-73001-9_80
DO - 10.1007/978-3-540-73001-9_80
M3 - Conference contribution
AN - SCOPUS:38149018390
SN - 9783540730002
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 748
EP - 757
BT - Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings
T2 - 3rd Conference on Computability in Europe, CiE 2007
Y2 - 18 June 2007 through 23 June 2007
ER -