Circuit Minimization Problem

Abstract

We study the complexity of the circuit minimization problem: given the truth table of a Boolean function f and a parameter s, decide whether f can be realized by a Boolean circuit of size at most s. We argue why this problem is unlikely to be in P (or even in P/poly) by giving a number of surprising consequences of such an assumption. We also argue that proving this problem to be NP-complete (if it is indeed true) would imply proving strong circuit lower bounds for the class E, which appears beyond the currently known techniques.

Versions

Extended abstract in Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 73-79, 2000.
Technical Report TR99-045, Electronic Colloquium on Computational Complexity.