The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k , is the circuit complexity of f at most k ? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of its kind, MCSP is not known to be N P -hard, yet an efficient algorithm for this problem also seems very unlikely: for example, MCSP P would imply there are no pseudorandom functions.

Although most N P -complete problems are complete under strong ``local'' reduction notions such as poly-logarithmic time projections, we show that MCSP is provably not N P -hard under O ( n 1 2 − ) -time projections, for every 0"> 0 . We prove that the N P -hardness of MCSP under (logtime-uniform) A C 0 reductions would imply extremely strong lower bounds: N P P pol y and E io-SIZE ( 2 n ) for some 0"> 0 (hence P = B P P also follows). We show that even the N P -hardness of MCSP under general polynomial-time reductions would separate complexity classes: EX P = N P P pol y which implies EX P = Z P P . These results help explain why it has been so difficult to prove that MCSP is N P -hard.

We also consider the nondeterministic generalization of MCSP: the Nondeterministic Minimum Circuit Size Problem (NMCSP), where one wishes to compute the nondeterministic circuit complexity of a given function. We prove that the 2 P -hardness of NMCSP, even under arbitrary polynomial-time reductions, would imply EX P P pol y .