On the complexity of the clone membership problem

Abstract

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öhler 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 }_2^P$-complete, and we complement Böhler 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 }_2^P$-complete (possibly under randomized reductions), coDP-complete, or in P.

30 pages