Circuit minimization problem

Valentine Kabanets and Jin-Yi Cai

---

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 (STOC'00), pages 73-79, 2000.
• technical report, in Electronic Colloquium on Computational Complexity TR99-045, 1999.

---