Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-045 | 24th April 2007 00:00

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

RSS-Feed




TR07-045
Authors: Heribert Vollmer
Publication: 16th May 2007 19:35
Downloads: 3804
Keywords: 


Abstract:

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