Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with projections:
TR14-164 | 30th November 2014
Cody Murray, Ryan Williams

On the (Non) NP-Hardness of Computing Circuit Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function $f$ and a size parameter $k$, is the circuit complexity of $f$ at most $k$? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of ... more >>>

ISSN 1433-8092 | Imprint