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 ... more >>>