Document Open Access Logo

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

Authors Lijie Chen, Dylan M. McKay, Cody D. Murray, R. Ryan Williams

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2019.30.pdf
  • Filesize: 0.73 MB
  • 21 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • Karp-Lipton Theorems
  • Circuit Lower Bounds
  • Derandomization
  • Hardness Magnification

Metrics

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

Abstract

A frontier open problem in circuit complexity is to prove P^{NP} is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P_{/poly}. Previously, for several classes containing P^{NP}, including NP^{NP}, ZPP^{NP}, and S_2 P, such lower bounds have been proved via Karp-Lipton-style Theorems: to prove C is not in SIZE[n^k] for all k, we show that C subset P_{/poly} implies a "collapse" D = C for some larger class D, where we already know D is not in SIZE[n^k] for all k. 
It seems obvious that one could take a different approach to prove circuit lower bounds for P^{NP} that does not require proving any Karp-Lipton-style theorems along the way. We show this intuition is wrong: (weak) Karp-Lipton-style theorems for P^{NP} are equivalent to fixed-polynomial size circuit lower bounds for P^{NP}. That is, P^{NP} is not in SIZE[n^k] for all k if and only if (NP subset P_{/poly} implies PH subset i.o.- P^{NP}_{/n}).
Next, we present new consequences of the assumption NP subset P_{/poly}, towards proving similar results for NP circuit lower bounds. We show that under the assumption, fixed-polynomial circuit lower bounds for NP, nondeterministic polynomial-time derandomizations, and various fixed-polynomial time simulations of NP are all equivalent. Applying this equivalence, we show that circuit lower bounds for NP imply better Karp-Lipton collapses. That is, if NP is not in SIZE[n^k] for all k, then for all C in {Parity-P, PP, PSPACE, EXP}, C subset P_{/poly} implies C subset i.o.-NP_{/n^epsilon} for all epsilon > 0. Note that unconditionally, the collapses are only to MA and not NP.
We also explore consequences of circuit lower bounds for a sparse language in NP. Among other results, we show if a polynomially-sparse NP language does not have n^{1+epsilon}-size circuits, then MA subset i.o.-NP_{/O(log n)}, MA subset i.o.-P^{NP[O(log n)]}, and NEXP is not in SIZE[2^{o(m)}]. Finally, we observe connections between these results and the "hardness magnification" phenomena described in recent works.

Cite As Get BibTex

Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.30

Author Details

Lijie Chen
  • MIT, Cambridge, MA, USA
Dylan M. McKay
  • MIT, Cambridge, MA, USA
Cody D. Murray
  • No Affiliation
R. Ryan Williams
  • MIT, Cambridge, MA, USA

Funding

Supported by NSF CCF-1741615 (Common Links in Algorithms and Complexity).

Acknowledgements

Part of this work was completed while three of the authors were visiting the Simons Institute at UC Berkeley, as part of the program on Lower Bounds in Computational Complexity. We thank them for their hospitality and excellent environment. We also thank Josh Alman for helpful last-minute proofreading, and the CCC reviewers for useful comments.

References

  1. Scott Aaronson. Oracles Are Subtle But Not Malicious. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 340-354, 2006. URL: https://doi.org/10.1109/CCC.2006.32.
  2. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1-14:36, 2010. URL: https://doi.org/10.1145/1706591.1706594.
  3. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  4. Vikraman Arvind, Johannes Köbler, Uwe Schöning, and Rainer Schuler. If NP has Polynomial-Size Circuits, then MA=AM. Theor. Comput. Sci., 137(2):279-282, 1995. URL: https://doi.org/10.1016/0304-3975(95)91133-B.
  5. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking Computations in Polylogarithmic Time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 21-31, 1991. URL: https://doi.org/10.1145/103418.103428.
  6. Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, and Christino Tamon. Oracles and Queries That Are Sufficient for Exact Learning. J. Comput. Syst. Sci., 52(3):421-433, 1996. URL: https://doi.org/10.1006/jcss.1996.0032.
  7. Harry Buhrman and Steven Homer. Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy. In Foundations of Software Technology and Theoretical Computer Science, 12th Conference, New Delhi, India, December 18-20, 1992, Proceedings, pages 116-127, 1992. URL: https://doi.org/10.1007/3-540-56287-7_99.
  8. Joshua Buresh-Oppenheim and Rahul Santhanam. Making Hard Problems Harder. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 73-87, 2006. URL: https://doi.org/10.1109/CCC.2006.26.
  9. Jin-yi Cai. S₂^P is subset of ZPP^NP. J. Comput. Syst. Sci., 73(1):25-35, 2007. URL: https://doi.org/10.1016/j.jcss.2003.07.015.
  10. Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, and Mitsunori Ogihara. Competing provers yield improved Karp-Lipton collapse results. Inf. Comput., 198(1):1-23, 2005. URL: https://doi.org/10.1016/j.ic.2005.01.002.
  11. Jin-yi Cai and Osamu Watanabe. On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy. SIAM J. Comput., 33(4):984-1009, 2004. URL: https://doi.org/10.1137/S0097539703422716.
  12. Venkatesan T Chakaravarthy and Sambuddha Roy. Oblivious symmetric alternation. In Annual Symposium on Theoretical Aspects of Computer Science, pages 230-241. Springer, 2006. Google Scholar
  13. Venkatesan T. Chakaravarthy and Sambuddha Roy. Arthur and Merlin as Oracles. Computational Complexity, 20(3):505-558, 2011. URL: https://doi.org/10.1007/s00037-011-0015-3.
  14. Lijie Chen. Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits. Electronic Colloquium on Computational Complexity (ECCC), 26:31, 2019. URL: https://eccc.weizmann.ac.il/report/2019/031.
  15. Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits "just beyond" known lower bounds. Electronic Colloquium on Computational Complexity (ECCC), 25:199, 2018. URL: https://eccc.weizmann.ac.il/report/2018/199.
  16. Peter Dixon, Aduri Pavan, and N. V. Vinodchandran. On Pseudodeterministic Approximation Algorithms. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pages 61:1-61:11, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.61.
  17. Lance Fortnow and Rahul Santhanam. Robust simulations and significant separations. Inf. Comput., 256:149-159, 2017. URL: https://doi.org/10.1016/j.ic.2017.07.002.
  18. Lance Fortnow, Rahul Santhanam, and Ryan Williams. Fixed-Polynomial Size Circuit Bounds. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 19-26, 2009. URL: https://doi.org/10.1109/CCC.2009.21.
  19. Oded Goldreich. Computational complexity - a conceptual perspective. Cambridge University Press, 2008. Google Scholar
  20. Juris Hartmanis, Neil Immerman, and Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, 65(2/3):158-181, 1985. URL: https://doi.org/10.1016/S0019-9958(85)80004-8.
  21. Russell Impagliazzo, 2018. Personal Communication. Google Scholar
  22. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson. Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Comput., 39(4):1637-1665, 2010. URL: https://doi.org/10.1137/080734030.
  23. Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. The Power of Natural Properties as Oracles. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 7:1-7:20, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.7.
  24. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci., 65(4):672-694, 2002. URL: https://doi.org/10.1016/S0022-0000(02)00024-7.
  25. Ravi Kannan. Circuit-Size Lower Bounds and Non-Reducibility to Sparse Sets. Information and Control, 55(1-3):40-56, 1982. URL: https://doi.org/10.1016/S0019-9958(82)90382-5.
  26. Richard Karp and Richard Lipton. Turing Machines That Take Advice. L'Enseignement Mathématique, 28(2):191-209, 1982. Google Scholar
  27. Johannes Köbler and Osamu Watanabe. New Collapse Consequences of NP Having Small Circuits. SIAM J. Comput., 28(1):311-324, 1998. URL: https://doi.org/10.1137/S0097539795296206.
  28. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic Methods for Interactive Proof Systems. J. ACM, 39(4):859-868, 1992. URL: https://doi.org/10.1145/146585.146605.
  29. Dylan McKay, Cody Murray, and Ryan Williams. Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes, 2019. To appear in STOC 2019. Google Scholar
  30. Cody Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 890-901, 2018. URL: https://doi.org/10.1145/3188745.3188910.
  31. Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds, 2019. To appear in CCC 2019. Google Scholar
  32. Igor Carboni Oliveira and Rahul Santhanam. Hardness Magnification for Natural Problems. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 65-76, 2018. URL: https://doi.org/10.1109/FOCS.2018.00016.
  33. Rahul Santhanam. Circuit Lower Bounds for Merlin-Arthur Classes. SIAM J. Comput., 39(3):1038-1061, 2009. URL: https://doi.org/10.1137/070702680.
  34. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. URL: https://doi.org/10.1137/0220053.
  35. Luca Trevisan and Salil P. Vadhan. Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity, 16(4):331-364, 2007. URL: https://doi.org/10.1007/s00037-007-0233-x.
  36. Christopher Umans. Pseudo-random generators for all hardnesses. J. Comput. Syst. Sci., 67(2):419-440, 2003. URL: https://doi.org/10.1016/S0022-0000(03)00046-1.
  37. N. V. Vinodchandran. A note on the circuit complexity of PP. Theor. Comput. Sci., 347(1-2):415-418, 2005. URL: https://doi.org/10.1016/j.tcs.2005.07.032.
  38. Chee-Keng Yap. Some Consequences of Non-Uniform Conditions on Uniform Classes. Theor. Comput. Sci., 26:287-300, 1983. URL: https://doi.org/10.1016/0304-3975(83)90020-8.
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