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.