- Home
- →
- Fakultäten
- →
- Fakultät für Elektrotechnik und Informatik
- →
- View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
Original version
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
Repository version
To cite the version in the repository, please use this identifier:
https://doi.org/10.15488/1988
Files in this item
| 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.
|
|
| License of this version: | CC BY-ND 2.0 Unported - https://creativecommons.org/licenses/by-nd/2.0/ |
| Publication type: | Article |
| Publishing status: | publishedVersion |
| Publication date: | 2012 |
| Keywords english: | boolean circuits, complexity classification, isomorphism, satisfiability problems, hierarchy |
| DDC: | 004 | Informatik |
This item appears in the following Collection(s):
-
Fakultät für Elektrotechnik und Informatik
Frei zugängliche Publikationen aus der Fakultät für Elektrotechnik und Informatik