%0 Journal Article
%T Complexity classifications for different equivalence and audit problems for Boolean circuits
%A Elmar B£¿£¿hler
%A Nadia Creignou
%A Matthias Galota
%A Steffen Reith
%A Henning Schnoor
%A Heribert Vollmer
%J Computer Science
%D 2010
%I arXiv
%R 10.2168/LMCS-8(3:31)2012
%X 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.
%U http://arxiv.org/abs/1009.1208v5