Document Open Access Logo

Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions

Authors Michael Saks, Rahul Santhanam

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2020.26.pdf
  • Filesize: 437 kB
  • 13 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
  • Theory of computation → Circuit complexity
  • Theory of computation → Complexity classes
Keywords
  • Minimum Circuit Size Problem
  • Turing reductions
  • circuit lower bounds

Metrics

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

Abstract

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.

Cite As Get BibTex

Michael Saks and Rahul Santhanam. Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.26

Author Details

Michael Saks
  • Rutgers University, Piscataway, NJ, USA
Rahul Santhanam
  • University of Oxford, UK

Funding

  • Santhanam, Rahul: This work was supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2014)/ERC Grant Agreement No. 615075.

References

  1. Eric Allender. The complexity of complexity. In Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, pages 79-94, 2017. Google Scholar
  2. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM J. Comput., 35(6):1467-1493, 2006. Google Scholar
  3. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. In Symposium on Mathematical Foundations of Computer Science (MFCS), pages 25-32, 2014. Google Scholar
  4. Eric Allender, Joshua A. Grochow, and Cristopher Moore. Graph isomorphism and circuit size. CoRR, abs/1511.08189, 2015. URL: http://arxiv.org/abs/1511.08189.
  5. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks. Minimizing DNF formulas and AC0 circuits given a truth table. Electronic Colloquium on Computational Complexity (ECCC), 126, 2005. Google Scholar
  6. Eric Allender and Shuichi Hirahara. New insights on the (non-)hardness of circuit minimization and related problems. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 54:1-54:14, 2017. Google Scholar
  7. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The minimum oracle circuit size problem. In International Symposium on Theoretical Aspects of Computer Science (STACS), pages 21-33, 2015. Google Scholar
  8. Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci., 77(1):14-40, 2011. Google Scholar
  9. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 1st edition, 2009. Google Scholar
  10. Sebastian Czort. The complexity of minimizing disjunctive normal form formulas. Master’s Thesis, University of Aarhus, 1999. Google Scholar
  11. Lance Fortnow and Rahul Santhanam. Robust simulations and significant separations. Information and Computation, 256:149-159, 2017. Google Scholar
  12. Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma. If NP languages are hard on the worst-case, then it is easy to find their hard instances. Computational Complexity, 16(4):412-441, 2007. Google Scholar
  13. Juris Hartmanis and Richard Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, pages 285-306, 1965. Google Scholar
  14. Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam. Np-hardness of minimum circuit size problem for OR-AND-MOD circuits. In 33rd Computational Complexity Conference, CCC 2018, pages 5:1-5:31, 2018. Google Scholar
  15. Shuichi Hirahara and Rahul Santhanam. On the average-case complexity of MCSP and its variants. In Computational Complexity Conference (CCC), pages 7:1-7:20, 2017. Google Scholar
  16. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In Conference on Computational Complexity (CCC), pages 18:1-18:20, 2016. Google Scholar
  17. John M. Hitchcock and Aduri Pavan. On the NP-completeness of the minimum circuit size problem. In Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pages 236-245, 2015. Google Scholar
  18. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Symposium on Theory of Computing (STOC), pages 73-79, 2000. Google Scholar
  19. Richard Karp and Richard Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 302-309, 1980. Google Scholar
  20. William J. Masek. Some NP-complete set covering problems. Unpublished Manuscript, 1979. Google Scholar
  21. Cody Murray and Ryan Williams. On the (non) NP-hardness of computing circuit complexity. In Conference on Computational Complexity (CCC), pages 365-380, 2015. Google Scholar
  22. Igor Carboni Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Computational Complexity Conference (CCC), pages 18:1-18:49, 2017. Google Scholar
  23. Alexander A. Razborov and Steven Rudich. Natural proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. Google Scholar
  24. Boris A. Trakhtenbrot. A survey of Russian approaches to perebor (brute-force searches) algorithms. IEEE Annals of the History of Computing, 6(4):384-400, 1984. Google Scholar
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