Circuit minimization problem
Valentine Kabanets, Jin‐Yi Cai · 2000
We study the complexity of the following 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 DTIME(2°('~)), which appears beyond the currently known techniques.Question: Is f,~ computable by a Boolean circuit of size at most sn?