Complexity classifications for different equivalence and audit problems for Boolean circuits

Elmar BÃ¶hler; Nadia Creignou; Matthias Galota; Steffen Reith; Henning Schnoor; Heribert Vollmer

doi:10.2168/LMCS-8(3:31)2012

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)2012

Complexity classifications for different equivalence and audit problems for Boolean circuitsArticle

Authors: Elmar BÃ¶hler ; Nadia Creignou ; Matthias Galota ; Steffen Reith ; Henning Schnoor ; Heribert Vollmer

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.

Comment: 25 pages, 1 figure

https://doi.org/10.2168/LMCS-8(3:31)2012

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

Licence: arXiv.org - Non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph