The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under “local” reductions computable in TIME($n^{0.49}$). The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) ... more >>>