 |
 |
Elmar Böhler ; Nadia Creignou ; Matthias Galota ; Steffen Reith ; Henning Schnoor et al.
-
Complexity classifications for different equivalence and audit problems
for Boolean circuits
lmcs:1172 -
Logical Methods in Computer Science,
September 30, 2012,
Volume 8, Issue 3
-
https://doi.org/10.2168/LMCS-8(3:31)2012Complexity classifications for different equivalence and audit problems
for Boolean circuitsArticle
We study Boolean circuits as a representation of Boolean functions and consider 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.
Source: arXiv.org:1009.1208
Volume: Volume 8, Issue 3
Published on: September 30, 2012
Imported on: July 25, 2011
Keywords: Computer Science - Computational Complexity,F.2.2
Funding:
- Source : OpenAIRE Graph
- BOOLE: Quantifying Boolean Frameworks; Funder: French National Research Agency (ANR); Code: ANR-09-BLAN-0011
Classifications
2 Documents citing this article
Consultation statistics
This page has been seen 2190 times.
This article's PDF has been downloaded 523 times.