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 $\co\NP$.