The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis

Heribert Vollmer

(Universität Hannover)

We study the complexity of the following algorithmic problem: Given a Boolean function $f$ and a finite set of Boolean functions $B$, decide if there is a circuit with basis $B$ that computes $f$. We show that if both $f$ and all functions in $B$ are given by their truth-table, the problem is in quasipolynomial-size AC$^0$, and thus cannot be hard for AC$^0(2)$ or any superclass like NC$^1$, L, or NL. This answers an open question by Bergman and Slutzki (SIAM J.~Comput., 2000). Furthermore we show that, if the input functions are not given by their truth-table but in a succinct way, i.e., by circuits (over any complete basis), the above problem becomes complete for the class coNP.
Thursday 15th March 2007, 14:00
Board Room
Department of Computer Science