2026-07-25T02:34:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5661 2024-03-06T10:36:44Z ddc:004 open_access

On the NP-Completeness of the Minimum Circuit Size Problem Hitchcock, John M. Pavan, A. Minimum Circuit Size NP-completeness truth-table reductions circuit complexity We study the Minimum Circuit Size Problem (MCSP): given the truth-table of a Boolean function f and a number k, does there exist a Boolean circuit of size at most k computing f? This is a fundamental NP problem that is not known to be NP-complete. Previous work has studied consequences of the NP-completeness of MCSP. We extend this work and consider whether MCSP may be complete for NP under more powerful reductions. We also show that NP-completeness of MCSP allows for amplification of circuit complexity. We show the following results. - If MCSP is NP-complete via many-one reductions, the following circuit complexity amplification result holds: If NP cap co-NP requires 2^n^{Omega(1)-size circuits, then E^NP requires 2^Omega(n)-size circuits. - If MCSP is NP-complete under truth-table reductions, then EXP neq NP cap SIZE(2^n^epsilon) for some epsilon> 0 and EXP neq ZPP. This result extends to polylog Turing reductions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik John M. Hitchcock and A. Pavan 2015 Is Part Of LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2015.236 urn:nbn:de:0030-drops-56613 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.236 eng https://creativecommons.org/licenses/by/3.0/legalcode