ECCC-Report TR07-045https://eccc.weizmann.ac.il/report/2007/045Comments and Revisions published for TR07-045en-usWed, 16 May 2007 19:35:10 +0300
Paper TR07-045
| The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis |
Heribert Vollmer
https://eccc.weizmann.ac.il/report/2007/045We 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$.
Wed, 16 May 2007 19:35:10 +0300https://eccc.weizmann.ac.il/report/2007/045