Computer Science/Discrete Mathematics Seminar I

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. We also prove new unconditional lower bounds for MKTP, by showing that MKTP is hard for the complexity class DET (a class that captures the complexity of computing the determinant; DET contains NL) under non-uniform $\mathrm{NC}^0$ reductions. (It is open whether these lower bounds also hold for MCSP.) Under a suitable derandomization hypothesis, we obtain uniform reductions, and we are even able to show that circuit size lower bounds are equivalent to hardness results for certain problems related to MKTP, and provide the first results showing that hardness of MCSP problems implies hardness for MKTP problems. Joint work with Shuichi Hirahara.