Complexity classifications for different equivalence and audit problems for Boolean circuits
Elmar Böhler, Nadia Creignou, Matthias Galota, Steffen Reith, Henning Schnoor, Heribert Vollmer · Logical Methods in Computer Science · 2012
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.