{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T14:04:13Z","timestamp":1770818653242,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T00:00:00Z","timestamp":1568246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1555409, CCF-1514164"],"award-info":[{"award-number":["CCF-1555409, CCF-1514164"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"JSPS KAKENHI","award":["JP16J06743"],"award-info":[{"award-number":["JP16J06743"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deal 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            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1 \u2212\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            is\n            <jats:italic>indeed<\/jats:italic>\n            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. Our technique is quite general; we use it also to show that approximating the size of the largest clique in a graph within a factor of\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1 \u2212\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            is also NP-intermediate unless NP\u2286 P\/poly.\n          <\/jats:p>\n          <jats:p>\n            We also prove that MKTP is hard for the complexity class DET under non-uniform NC\n            <jats:sup>0<\/jats:sup>\n            reductions. This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of \u201clocal\u201d reductions such as \u2264\n            <jats:sup>\n              NC\n              <jats:sup>0<\/jats:sup>\n            <\/jats:sup>\n            <jats:sub>m<\/jats:sub>\n            . We exploit this local reduction to obtain several new consequences:\n          <\/jats:p>\n          <jats:p>\n            \u2014 MKTP is not in AC\n            <jats:sup>0<\/jats:sup>\n            [\n            <jats:italic>p<\/jats:italic>\n            ].\n          <\/jats:p>\n          <jats:p>\n            \u2014 Circuit size lower bounds are equivalent to hardness of a relativized version MKTP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            of MKTP under a class of uniform AC\n            <jats:sup>0<\/jats:sup>\n            reductions, for a significant class of sets\n            <jats:italic>A<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            \u2014 Hardness of MCSP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            implies hardness of MCSP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            for a significant class of sets\n            <jats:italic>A<\/jats:italic>\n            . This is the first result directly relating the complexity of MCSP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            and MCSP\n            <jats:sup>\n              <jats:italic>A<\/jats:italic>\n            <\/jats:sup>\n            , for any\n            <jats:italic>A<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3349616","type":"journal-article","created":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T12:28:56Z","timestamp":1568377736000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems"],"prefix":"10.1145","volume":"11","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[{"name":"Rutgers University, Piscataway, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuichi","family":"Hirahara","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Chiyoda-ku, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.003"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1583"},{"key":"e_1_2_1_3_1","volume-title":"The permanent requires large uniform threshold circuits. Chicago J. Theor. Comput. Sci","author":"Allender Eric","year":"1999","unstructured":"Eric Allender . 1999. The permanent requires large uniform threshold circuits. Chicago J. Theor. Comput. Sci . 1999 , Article 7 (1999), 1--19. Eric Allender. 1999. The permanent requires large uniform threshold circuits. Chicago J. Theor. Comput. Sci. 1999, Article 7 (1999), 1--19."},{"key":"e_1_2_1_4_1","volume-title":"Complexity of Computations and Proofs","author":"Allender Eric","unstructured":"Eric Allender . 2004. Arithmetic circuits and counting complexity classes . In Complexity of Computations and Proofs , J. Kraj\u00ed\u010dek (Ed.). Quaderni di Matematica, Vol. 13 . Seconda Universit\u00e0 di Napoli , 33--72. Eric Allender. 2004. Arithmetic circuits and counting complexity classes. In Complexity of Computations and Proofs, J. Kraj\u00ed\u010dek (Ed.). Quaderni di Matematica, Vol. 13. Seconda Universit\u00e0 di Napoli, 33--72."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628994"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.04.004"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157970"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0124-0"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706594"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/872746.873133"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1996300100011"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a026"},{"key":"e_1_2_1_15_1","series-title":"Lecture Notes in Computer Science","volume-title":"Theoretical Computer Science, Essays in Memory of Shimon Even","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2006. On promise problems: A survey . In Theoretical Computer Science, Essays in Memory of Shimon Even , Lecture Notes in Computer Science , Vol. 3895 , Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (Eds.). Springer , 254--290. Oded Goldreich. 2006. On promise problems: A survey. In Theoretical Computer Science, Essays in Memory of Shimon Even, Lecture Notes in Computer Science, Vol. 3895, Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (Eds.). Springer, 254--290."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 18th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Hagerup Torben","unstructured":"Torben Hagerup . 1991. Fast parallel generation of random permutations . In Proceedings of the 18th International Colloquium on Automata, Languages and Programming (ICALP) , Lecture Notes in Computer Science , Vol. 510 . Springer , 405--416. Torben Hagerup. 1991. Fast parallel generation of random permutations. In Proceedings of the 18th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, Vol. 510. Springer, 405--416."},{"key":"e_1_2_1_18_1","volume-title":"Computational Limitations for Small Depth Circuits","author":"H\u00e5stad Johan","unstructured":"Johan H\u00e5stad . 1987. Computational Limitations for Small Depth Circuits . MIT Press , Cambridge, MA . Johan H\u00e5stad. 1987. Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 32nd Conference on Computational Complexity (CCC), LIPIcs","volume":"79","author":"Hirahara Shuichi","year":"2017","unstructured":"Shuichi Hirahara and Rahul Santhanam . 2017 . On the average-case complexity of MCSP and its variants . In Proceedings of the 32nd Conference on Computational Complexity (CCC), LIPIcs , Vol. 79 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 7:1--7:20. Shuichi Hirahara and Rahul Santhanam. 2017. On the average-case complexity of MCSP and its variants. In Proceedings of the 32nd Conference on Computational Complexity (CCC), LIPIcs, Vol. 79. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 7:1--7:20."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC), LIPIcs","volume":"50","author":"Hirahara Shuichi","year":"2016","unstructured":"Shuichi Hirahara and Osamu Watanabe . 2016 . Limits of minimum circuit size problem as oracle . In Proceedings of the 31st Conference on Computational Complexity (CCC), LIPIcs , Vol. 50 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 18:1--18:20. Shuichi Hirahara and Osamu Watanabe. 2016. Limits of minimum circuit size problem as oracle. In Proceedings of the 31st Conference on Computational Complexity (CCC), LIPIcs, Vol. 50. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 18:1--18:20."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST8TCS), LIPIcs","volume":"45","author":"John","unstructured":"John M. Hitchcock and Aduri Pavan. 2015. On the NP-completeness of the minimum circuit size problem . In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST8TCS), LIPIcs , Vol. 45 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 236--245. John M. Hitchcock and Aduri Pavan. 2015. On the NP-completeness of the minimum circuit size problem. In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST8TCS), LIPIcs, Vol. 45. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 236--245."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 33rd Conference on Computational Complexity (CCC), LIPIcs","volume":"102","author":"Impagliazzo R.","unstructured":"R. Impagliazzo , V. Kabanets , and I. Volkovich . 2018. The power of natural properties as oracles . In Proceedings of the 33rd Conference on Computational Complexity (CCC), LIPIcs , Vol. 102 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 7:1--7:20. R. Impagliazzo, V. Kabanets, and I. Volkovich. 2018. The power of natural properties as oracles. In Proceedings of the 33rd Conference on Computational Complexity (CCC), LIPIcs, Vol. 102. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 7:1--7:20."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335314"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683260"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a004"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 32nd Conference on Computational Complexity (CCC), LIPIcs","volume":"79","author":"Oliveira Igor","year":"2017","unstructured":"Igor Oliveira and Rahul Santhanam . 2017 . Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness . In Proceedings of the 32nd Conference on Computational Complexity (CCC), LIPIcs , Vol. 79 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 18:1--18:49. Igor Oliveira and Rahul Santhanam. 2017. Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness. In Proceedings of the 32nd Conference on Computational Complexity (CCC), LIPIcs, Vol. 79. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 18:1--18:49."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1991.160253"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_2_1_37_1","first-page":"598","article-title":"Lower bounds on the size of bounded depth networks over a complete basis with logical addition","volume":"41","author":"Razborov Alexander A.","year":"1987","unstructured":"Alexander A. Razborov . 1987 . Lower bounds on the size of bounded depth networks over a complete basis with logical addition . Mat. Zametki 41 , 598 -- 607 . In Russian. English translation in Math. Notes o Acad. Sci. USSR 41:333--338, 1987. Alexander A. Razborov. 1987. Lower bounds on the size of bounded depth networks over a complete basis with logical addition. Mat. Zametki 41, 598--607. In Russian. English translation in Math. Notes o Acad. Sci. USSR 41:333--338, 1987.","journal-title":"Mat. Zametki"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.07.005"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00110-7"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116858"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970241096X"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447207"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0187-1"},{"key":"e_1_2_1_45_1","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"Vollmer Heribert","unstructured":"Heribert Vollmer . 1999. Introduction to Circuit Complexity: A Uniform Approach . Springer-Verlag , New York . Heribert Vollmer. 1999. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag, New York."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3349616","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3349616","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3349616","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:19Z","timestamp":1750202599000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3349616"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,12]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3349616"],"URL":"https:\/\/doi.org\/10.1145\/3349616","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,12]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}