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.