Böhler, Elmar and Creignou, Nadia and Galota, Matthias and Reith, Steffen and Schnoor, Henninget 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
Complexity classifications for different equivalence and audit problems for Boolean circuits

Authors: Böhler, Elmar and Creignou, Nadia and Galota, Matthias and Reith, Steffen and Schnoor, Henning and Vollmer, Heribert

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 : oai:arXiv.org:1009.1208
DOI : 10.2168/LMCS-8(3:31)2012
Volume: Volume 8, Issue 3
Published on: September 30, 2012
Submitted on: July 25, 2011
Keywords: Computer Science - Computational Complexity,F.2.2


Share

Consultation statistics

This page has been seen 77 times.
This article's PDF has been downloaded 58 times.