- Startseite
- →
- Fakultäten
- →
- Fakultät für Elektrotechnik und Informatik
- →
- Dokumentanzeige
JavaScript is disabled for your browser. Some features of this site may not work without it.
Originalpublikation
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
Version im Repositorium
Zum Zitieren der Version im Repositorium verwenden Sie bitte diesen DOI:
https://doi.org/10.15488/1988
| Zusammenfassung: | |
|
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.
|
|
| Lizenzbestimmungen: | CC BY-ND 2.0 Unported - https://creativecommons.org/licenses/by-nd/2.0/ |
| Publikationstyp: | Article |
| Publikationsstatus: | publishedVersion |
| Erstveröffentlichung: | 2012 |
| Schlagwörter (englisch): | boolean circuits, complexity classification, isomorphism, satisfiability problems, hierarchy |
| Fachliche Zuordnung (DDC): | 004 | Informatik |
Die Publikation erscheint in Sammlung(en):
-
Fakultät für Elektrotechnik und Informatik
Frei zugängliche Publikationen aus der Fakultät für Elektrotechnik und Informatik