dc.identifier.uri |
http://dx.doi.org/10.15488/1988 |
|
dc.identifier.uri |
http://www.repo.uni-hannover.de/handle/123456789/2013 |
|
dc.contributor.author |
Boehler, Elmar
|
|
dc.contributor.author |
Creignou, Nadia
|
|
dc.contributor.author |
Galota, Matthias
|
|
dc.contributor.author |
Reith, Steffen
|
|
dc.contributor.author |
Schnoor, Henning
|
|
dc.contributor.author |
Vollmer, Heribert
|
|
dc.date.accessioned |
2017-10-10T07:24:39Z |
|
dc.date.available |
2017-10-10T07:24:39Z |
|
dc.date.issued |
2012 |
|
dc.identifier.citation |
Boehler, Elmar; Creignou, Nadia; Galota, Matthias; Reith, Steffen; Schnoor, Henning et al.: Complexity classifications for different equivalence and audit problems for boolean circuits. In: Logical Methods in Computer Science 8 (2012), Nr. 3, 31. DOI: https://doi.org/10.2168/LMCS-8(3:31)2012 |
|
dc.description.abstract |
We study Boolean circuits as a representation of Boolean functions and conskier different equivalence, audit, and enumeration problems. For a number of restricted sets of gate types (bases) we obtain efficient algorithms, while for all other gate types we show these problems are at least NP-hard. |
eng |
dc.language.iso |
eng |
|
dc.publisher |
Braunschweig : Tech. Univ. Braunschweig |
|
dc.relation.ispartofseries |
Logical Methods in Computer Science 8 (2012), Nr. 3 |
|
dc.rights |
CC BY-ND 2.0 Unported |
|
dc.rights.uri |
https://creativecommons.org/licenses/by-nd/2.0/ |
|
dc.subject |
boolean circuits |
eng |
dc.subject |
complexity classification |
eng |
dc.subject |
isomorphism |
eng |
dc.subject |
satisfiability problems |
eng |
dc.subject |
hierarchy |
eng |
dc.subject.ddc |
004 | Informatik
|
ger |
dc.title |
Complexity classifications for different equivalence and audit problems for boolean circuits |
eng |
dc.type |
Article |
|
dc.type |
Text |
|
dc.relation.issn |
1860-5974 |
|
dc.relation.doi |
https://doi.org/10.2168/LMCS-8(3:31)2012 |
|
dc.bibliographicCitation.issue |
3 |
|
dc.bibliographicCitation.volume |
8 |
|
dc.bibliographicCitation.firstPage |
31 |
|
dc.description.version |
publishedVersion |
|
tib.accessRights |
frei zug�nglich |
|