Details
| Original language | English |
|---|---|
| Title of host publication | Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings |
| Pages | 748-757 |
| Number of pages | 10 |
| Publication status | Published - 2007 |
| Event | 3rd Conference on Computability in Europe, CiE 2007 - Siena, Italy Duration: 18 Jun 2007 → 23 Jun 2007 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 4497 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 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.
Keywords
- Clone, Computational complexity, Constraint satisfaction, Galois connection, Polymorphism, Satisfiability problems
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- General Computer Science
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings. 2007. p. 748-757 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4497 LNCS).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › 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 -