## New insights on the (non)-hardness of circuit minimization and related problems

Eric Allender

Rutgers University

February 27, 2017

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We present new results relating the complexity of various approximation problems related to MCSP and MKTP. We show that, under modest cryptographic assumptions, some of these approximation problems must have intermediate complexity: they have no solution in P/poly and are not NP-hard under P/poly reductions.