2026-10-18T00:59:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8063 2024-03-06T09:40:56Z ddc:004 open_access

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems Allender, Eric Hirahara, Shuichi computational complexity Kolmogorov complexity circuit size 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Allender and Shuichi Hirahara 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.54 urn:nbn:de:0030-drops-80636 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.54 eng https://creativecommons.org/licenses/by/3.0/legalcode