Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with clone:
TR07-045 | 24th April 2007
Heribert Vollmer

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

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, ... more >>>

ISSN 1433-8092 | Imprint