Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-045 | 24th April 2007 00:00

The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis


Authors: Heribert Vollmer
Publication: 16th May 2007 19:35
Downloads: 1590


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$.

ISSN 1433-8092 | Imprint