  We investigate the complexity of the Boolean clone membership problem (CMP):
given a set of Boolean functions $F$ and a Boolean function $f$, determine if
$f$ is in the clone generated by $F$, i.e., if it can be expressed by a circuit
with $F$-gates. Here, $f$ and elements of $F$ are given as circuits or formulas
over the usual De Morgan basis. B\"ohler and Schnoor (2007) proved that for any
fixed $F$, the problem is coNP-complete, with a few exceptions where it is in
P. Vollmer (2009) incorrectly claimed that the full problem CMP is also
coNP-complete. We prove that CMP is in fact $\Theta^P_2$-complete, and we
complement B\"ohler and Schnoor's results by showing that for fixed $f$, the
problem is NP-complete unless $f$ is a projection.
  More generally, we study the problem $B$-CMP where $F$ and $f$ are given by
circuits using gates from $B$. For most choices of $B$, we classify the
complexity of $B$-CMP as being $\Theta^P_2$-complete (possibly under randomized
reductions), coDP-complete, or in P.
