ECCC-Report TR17-073https://eccc.weizmann.ac.il/report/2017/073Comments and Revisions published for TR17-073en-usFri, 28 Apr 2017 04:49:40 +0300
Paper TR17-073
| New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems |
Eric Allender,
Shuichi Hirahara
https://eccc.weizmann.ac.il/report/2017/073The 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 show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) within a factor of $n^{1 - o(1)}$ is indeed NP-intermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function.
We also prove that MKTP is hard for the complexity class DET under non-uniform NC$^0$ reductions. This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of "local" reductions (such as NC$^0$ reductions).
We exploit this local reduction to obtain several new consequences:
* MKTP is not in AC$^0[p]$.
* Circuit size lower bounds are equivalent to hardness of a relativized version MKTP$^A$ of MKTP under a class of uniform AC$^0$ reductions, for a large class of sets A.
* Hardness of MCSP$^A$ implies hardness of MKTP$^A$ for a wide class of sets A. This is the first result directly relating the complexity of MCSP$^A$ and MKTP$^A$, for any A.Fri, 28 Apr 2017 04:49:40 +0300https://eccc.weizmann.ac.il/report/2017/073