Document Open Access Logo

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems

Authors Eric Allender, Shuichi Hirahara

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2017.54.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • computational complexity
  • Kolmogorov complexity
  • circuit size

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Eric Allender and Shuichi Hirahara. New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.54

Author Details

Eric Allender
Shuichi Hirahara

References

  1. Manindra Agrawal. The isomorphism conjecture for constant depth reductions. Journal of Computer and System Sciences, 77(1):3-13, 2011. URL: http://dx.doi.org/10.1145/28395.28404.
  2. Manindra Agrawal, Eric Allender, and Steven Rudich. Reductions in circuit complexity: An isomorphism theorem and a gap theorem. Journal of Computer and System Sciences, 57(2):127-143, 1998. URL: http://dx.doi.org/10.1006/jcss.1998.1583.
  3. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM Journal on Computing, 35:1467-1493, 2006. URL: http://dx.doi.org/10.1137/050628994.
  4. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. Information and Computation, 2017. to appear. URL: http://dx.doi.org/10.1016/j.ic.2017.04.004.
  5. Eric Allender, Joshua Grochow, and Cristopher Moore. Graph isomorphism and circuit size. Technical Report TR15-162, Electronic Colloquium on Computational Complexity, 2015. URL: https://eccc.weizmann.ac.il/report/2015/162/.
  6. Eric Allender and Shuichi Hirahara. New insights on the (non)-hardness of circuit minimization and related problems. Technical Report TR17-073, Electronic Colloquium on Computational Complexity, 2017. URL: https://eccc.weizmann.ac.il/report/2017/073/.
  7. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The minimum oracle circuit size problem. Computational Complexity, 26(2):469-496, 2017. URL: http://dx.doi.org/10.1007/s00037-016-0124-0.
  8. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. Journal of the ACM, 57:14:1-14:36, 2010. URL: http://dx.doi.org/10.1145/1706591.1706594.
  9. Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. Journal of Computer and System Sciences, 77:14-40, 2010. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.004.
  10. Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola. On beating the hybrid argument. Theory of Computing, 9:809-843, 2013. URL: http://dx.doi.org/10.4086/toc.2013.v009a026.
  11. Oded Goldreich. On promise problems: A survey. In Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman, editors, Theoretical Computer Science, Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, pages 254-290. Springer, 2006. URL: http://dx.doi.org/10.1007/11685654_12.
  12. Johan Håstad. Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA, 1987. Google Scholar
  13. Shuichi Hirahara and Rahul Santhanam. On the average-case complexity of mcsp and its variants. In 32nd Conference on Computational Complexity, CCC, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. to appear. Google Scholar
  14. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In 31st Conference on Computational Complexity, CCC, LIPIcs, pages 18:1-10:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.18.
  15. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In STOC'97, pages 220-229, 1997. URL: http://dx.doi.org/10.1145/258533.258590.
  16. Valentine Kabanets and Jin-Yi Cai. Circuit minimization problem. In ACM Symposium on Theory of Computing (STOC), pages 73-79, 2000. URL: http://dx.doi.org/10.1145/335305.335314.
  17. Adam Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing, 31(5):1501-1526, 2002. URL: http://dx.doi.org/10.1137/S0097539700389652.
  18. Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155-171, 1975. URL: http://dx.doi.org/10.1145/321864.321877.
  19. Cody Murray and Ryan Williams. On the (non) NP-hardness of computing circuit complexity. In 30th Conference on Computational Complexity, CCC, volume 33 of LIPIcs, pages 365-380. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.365.
  20. Igor Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness. In 32nd Conference on Computational Complexity, CCC, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. to appear. Google Scholar
  21. Rafail Ostrovsky. One-way functions, hard on average problems, and statistical zero-knowledge proofs. In IEEE Conference on Structure in Complexity Theory, pages 133-138. IEEE Computer Society, 1991. URL: http://dx.doi.org/10.1109/SCT.1991.160253.
  22. Rafail Ostrovsky and Avi Wigderson. One-way fuctions are essential for non-trivial zero-knowledge. In Second Israel Symposium on Theory of Computing Systems (ISTCS), pages 3-17. IEEE Computer Society, 1993. URL: http://dx.doi.org/10.1109/ISTCS.1993.253489.
  23. Alexander Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55:24-35, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1494.
  24. Alexander A. Razborov. Lower bounds on the size of bounded depth networks over a complete basis with logical addition. Matematicheskie Zametki, 41:598-607, 1987. In Russian. English translation in Mathematical Notes of the Academy of Sciences of the USSR 41:333-338, 1987. Google Scholar
  25. Michael Rudow. Discrete logarithm and minimum circuit size. Technical Report TR16-23, Electronic Colloquium on Computational Complexity, 2016. URL: https://eccc.weizmann.ac.il/report/2016/108/.
  26. Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings 19th Symposium on Theory of Computing, pages 77-8. ACM Press, 1987. URL: http://dx.doi.org/10.1145/28395.28404.
  27. Jacobo Torán. On the hardness of graph isomorphism. SIAM Journal on Computing, 33(5):1093-1108, 2004. URL: http://dx.doi.org/10.1137/S009753970241096X.
  28. Salil P. Vadhan. An unconditional study of computational zero knowledge. SIAM Journal on Computing, 36(4):1160-1214, 2006. URL: http://dx.doi.org/10.1137/S0097539705447207.
  29. Heribert Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York Inc., 1999. URL: http://dx.doi.org/10.1007/978-3-662-03927-4.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact