Complexity classifications for different equivalence and audit problems for Boolean circuits

Elmar B\~A{\P}hler (Universit\"at W\"urzburg); Henning Schnoor (Christian-Albrechts-Universit\"at zu Kiel); Heribert Vollmer (Leibniz Universit\"at Hannover); Marseille); Matthias Galota (Elektrobit); Nadia Creignou (Universit\'e de la M\'editerran\'ee; Steffen Reith (Hochschule RheinMain; Wiesbaden)

arxiv: 1009.1208 · v5 · pith:SSZDQVWQnew · submitted 2010-09-07 · 💻 cs.CC

Complexity classifications for different equivalence and audit problems for Boolean circuits

Elmar B\~A{\P}hler (Universit\"at W\"urzburg) , Nadia Creignou (Universit\'e de la M\'editerran\'ee , Marseille) , Matthias Galota (Elektrobit) , Steffen Reith (Hochschule RheinMain , Wiesbaden) , Henning Schnoor (Christian-Albrechts-Universit\"at zu Kiel) , Heribert Vollmer (Leibniz Universit\"at Hannover) This is my paper

classification 💻 cs.CC

keywords booleanproblemsauditcircuitsdifferentequivalencegatetypes

0 comments

read the original 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.

This paper has not been read by Pith yet.

Complexity classifications for different equivalence and audit problems for Boolean circuits

discussion (0)