Complexity classifications for different equivalence and audit problems for Boolean circuits
- Publisher: Tech. Univ. Braunschweig
satisfiability problems | Informatik | Computer Science - Computational Complexity | hierarchy | boolean circuits | complexity classification | F.2.2 | isomorphism
arxiv: Computer Science::Hardware Architecture | Computer Science::Emerging Technologies
We study Boolean circuits as a representation of Boolean functions and conskier 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.