- Record: found
- Abstract: found
- Article: found
Complexity classifications for different equivalence and audit problems for Boolean circuits
Preprint
Elmar Böhler ,
Nadia Creignou ,
Matthias Galota ,
Steffen Reith ,
Henning Schnoor ,
Heribert Vollmer
2010-09-07
Read this article at
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.
Abstract
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.
Related collections
Most cited references11
- Record: found
- Abstract: not found
- Article: not found
The circuit value problem is log space complete for P
Richard Ladner (1975)