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.

    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
    • BOOLE: Quantifying Boolean Frameworks; Funder: French National Research Agency (ANR); Code: ANR-09-BLAN-0011

    2 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 1249 times.
    This article's PDF has been downloaded 428 times.