Details
| Original language | English |
|---|---|
| Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Editors | Volker Diekert, Michel Habib |
| Publisher | Springer Verlag |
| Pages | 164-175 |
| Number of pages | 12 |
| ISBN (print) | 9783540212362 |
| Publication status | Published - 2004 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 2996 |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
Abstract
We consider the Boolean constraint isomorphism problem, that is, the problem of determining whether two sets of Boolean constraint applications can be made equivalent by renaming the variables. We show that depending on the set of allowed constraints, the problem is either coNP-hard and GI-hard, equivalent to graph isomorphism, or polynomial-time solvable. This establishes a complete classification of the complexity of the problem, and moreover, it identifies exactly all those cases in which Boolean constraint isomorphism is polynomial-time manyone equivalent to graph isomorphism, the best-known and best-examined isomorphism problem in theoretical computer science.
Keywords
- cs.CC, cs.LO, F.1.3;F.4.1
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- General Computer Science
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Volker Diekert; Michel Habib. Springer Verlag, 2004. p. 164-175 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2996).
Research output: Chapter in book/report/conference proceeding › Contribution to book/anthology › Research › peer review
}
TY - CHAP
T1 - The complexity of Boolean constraint isomorphism
AU - Böhler, Elmar
AU - Hemaspaandra, Edith
AU - Reith, Steffen
AU - Vollmer, Heribert
PY - 2004
Y1 - 2004
N2 - We consider the Boolean constraint isomorphism problem, that is, the problem of determining whether two sets of Boolean constraint applications can be made equivalent by renaming the variables. We show that depending on the set of allowed constraints, the problem is either coNP-hard and GI-hard, equivalent to graph isomorphism, or polynomial-time solvable. This establishes a complete classification of the complexity of the problem, and moreover, it identifies exactly all those cases in which Boolean constraint isomorphism is polynomial-time manyone equivalent to graph isomorphism, the best-known and best-examined isomorphism problem in theoretical computer science.
AB - We consider the Boolean constraint isomorphism problem, that is, the problem of determining whether two sets of Boolean constraint applications can be made equivalent by renaming the variables. We show that depending on the set of allowed constraints, the problem is either coNP-hard and GI-hard, equivalent to graph isomorphism, or polynomial-time solvable. This establishes a complete classification of the complexity of the problem, and moreover, it identifies exactly all those cases in which Boolean constraint isomorphism is polynomial-time manyone equivalent to graph isomorphism, the best-known and best-examined isomorphism problem in theoretical computer science.
KW - cs.CC
KW - cs.LO
KW - F.1.3;F.4.1
UR - http://www.scopus.com/inward/record.url?scp=35048820484&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-24749-4_15
DO - 10.1007/978-3-540-24749-4_15
M3 - Contribution to book/anthology
AN - SCOPUS:35048820484
SN - 9783540212362
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 164
EP - 175
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Diekert, Volker
A2 - Habib, Michel
PB - Springer Verlag
ER -