2026-07-23T17:35:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12578 2024-03-06T10:50:29Z ddc:004 open_access

Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions Saks, Michael Santhanam, Rahul Minimum Circuit Size Problem Turing reductions circuit lower bounds The fundamental Minimum Circuit Size Problem is a well-known example of a problem that is neither known to be in 𝖯 nor known to be NP-hard. Kabanets and Cai [Kabanets and Cai, 2000] showed that if MCSP is NP-hard under "natural" m-reductions, superpolynomial circuit lower bounds for exponential time would follow. This has triggered a long line of work on understanding the power of reductions to MCSP. Nothing was known so far about consequences of NP-hardness of MCSP under general Turing reductions. In this work, we consider two structured kinds of Turing reductions: parametric honest reductions and natural reductions. The latter generalize the natural reductions of Kabanets and Cai to the case of Turing-reductions. We show that NP-hardness of MCSP under these kinds of Turing-reductions imply superpolynomial circuit lower bounds for exponential time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Saks and Rahul Santhanam 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.26 urn:nbn:de:0030-drops-125786 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode