Advertisement
Published in:
20-01-2021
On the Complexity of the Clone Membership Problem
Published in: Theory of Computing Systems | Issue 5/2021
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 (Theory Comput. Syst. 41(4):753–777, 2007) proved that for any fixed F, the problem is coNP-complete, with a few exceptions where it is in P. Vollmer (Theory Comput. Syst. 44(1): 82–90, 2009) incorrectly claimed that the full problem CMP is also coNP-complete. We prove that CMP is in fact \(\boldsymbol {\Theta }^{\mathbf {P}}_{2}\)-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 \(\boldsymbol {\Theta }^{\mathbf {P}}_2\)-complete (possibly under randomized reductions), coDP-complete, or in P.