[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The Power of Natural Properties as Oracles

  • Published:
computational complexity Aims and scope Submit manuscript

Abstract

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We show that in a number of complexity-theoretic results that use the SAT oracle, one can use the MCSP oracle instead. For example, we show that \(\mathsf{ZPEXP}^\mathsf{MCSP}\nsubseteq \mathsf{P} / \mathsf {poly}\), which should be contrasted with the previously known circuit lower bound \(\mathsf{ZPEXP}^\mathsf{NP}\nsubseteq \mathsf{P} / \mathsf{poly}\). We also show that, assuming the existence of indistinguishability obfuscators (IOs), SAT and MCSP are equivalent in the sense that one has an efficient randomized (BPP) algorithm if and only if the other one does. We interpret our results as providing some evidence that MCSP may be NP-hard under randomized polynomial-time reductions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • L. M. Adleman (1978). Two Theorems on Random Polynomial Time. In Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 75–83.

  • E. Allender, H. Buhrman, M.l Koucký, D. van Melkebeek & D. Ronneburger (2006). Power from Random Strings. SIAM J. Comput. 35(6), 1467–1493. URL http://dx.doi.org/10.1137/050628994.

  • E. Allender & B. Das (2014). Zero Knowledge and Circuit Minimization. In Mathematical Foundations of Computer Scienc MFCS, 25–32.

  • E. Allender, L. Hellerstein, P. McCabe, T. Pitassi & M. E. Saks (2008). Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. SIAM J. Comput. 38(1), 63–84. URL http://dx.doi.org/10.1137/060664537.

  • E. Allender, D. Holden & V. Kabanets (2015). The Minimum Oracle Circuit Size Problem. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, 21–33. URL http://dx.doi.org/10.4230/LIPIcs.STACS.2015.21.

  • S. Arora & B. Barak (2009). Computational complexity: a modern approach. Cambridge University Press.

  • V. Arvind & J. Köbler (2001). On pseudorandomness and resourcebounded measure. Theor. Comput. Sci. 255(1-2), 205–221.

  • L. Babai, L. Fortnow & C. Lund (1991). Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols. Computational Complexity 1, 3–40.

  • L. Babai, L. Fortnow, N. Nisan & A. Wigderson (1993). BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity 3, 307–318.

  • B. Barak (2002). A Probabilistic-Time Hierarchy Theorem for ”Slightly Non-uniform” Algorithms. In RANDOM, 194–208.

  • B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan & K. Yang (2001). On the (Im)possibility of Obfuscating Programs. In Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, 1–18.

  • D. Beaver & J. Feigenbaum (1990). Hiding Instances in Multioracle Queries. In STACS, 37–48. URL http://dx.doi.org/10.1007/3-540-52282-4_30.

  • N. H. Bshouty, R. Cleve, R. Gavaldà, S. Kannan & C. Tamon (1996). Oracles and Queries That Are Sufficient for Exact Learning. J. Comput. Syst. Sci. 52(3), 421–433.

  • H. Buhrman, L. Fortnow & T. Thierauf (1998). Nonrelativizing Separations. In Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC), 8–12.

  • H. Buhrman & S. Homer (1992). 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, 116–127. URL http://dx.doi.org/10.1007/3-540-56287-7_99.

  • M. L. Carmosino, R. Impagliazzo, V. Kabanets & A. Kolokolova (2016). Learning Algorithms from Natural Proofs. In Proceedings of the 31st Conference on Computational Complexity, CCC, 1–24.

  • J. Feigenbaum & L. Fortnow (1993). Random-self-reducibility of complete sets. SIAM J. on Computing 22(5), 994–1005. ISSN 0097-5397.

  • L. Fortnow & A. R. Klivans (2009). Efficient learning algorithms yield circuit lower bounds. J. Comput. Syst. Sci. 75(1), 27–36.

  • L. Fortnow & R. Santhanam (2004). Hierarchy Theorems for Probabilistic Polynomial Time. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 316–324.

  • O. Goldreich & D. Zuckerman (2011). Another Proof That BPP \(\subseteq\) PH (and More). Studies in Complexity and Cryptography 40–53.

  • S. Goldwasser & G. N. Rothblum (2014). On Best-Possible Obfuscation. J. Cryptol. 27(3), 480–505. URL https://doi.org/10.1007/s00145-013-9151-z.

  • H. Heller (1986). On Relativized Exponential and Probabilistic Complexity Classes. Information and Control 71(3), 231–243. URL http://dx.doi.org/10.1016/S0019-9958(86)80012-2.

  • Sh. Hirahara & O. Watanabe (2016). Limits of Minimum Circuit Size Problem as Oracle. In 31st Conference on Computational Complexity, CCC, 18:1–18:20. URL http://dx.doi.org/10.4230/LIPIcs.CCC.2016.18.

  • J. M. Hitchcock & A. Pavan (2015). On the NP-Completeness of the Minimum Circuit Size Problem. In 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS, 236–245. URL http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.236.

  • R. Ilango (2020a). Approaching MCSP from Above and Below: Hardness for a Conditional Variant and ACˆ0[p]. In 11th Innovations in Theoretical Computer Science Conference, ITCS, volume 151 of LIPIcs, 34:1–34:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL https://doi.org/10.4230/LIPIcs.ITCS.2020.34.

  • R. Ilango (2020b). Constant Depth Formula and Partial Function Versions of MCSP are Hard. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, 424–433. IEEE.

  • R. Ilango, B. Loff & I. Carboni Oliveira (2020). NP-Hardness of Circuit Minimization for Multi-Output Functions. In 35th Conference on Computational Complexity, CCC, volume 169 of LIPIcs, 22:1–22:36. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

  • R. Impagliazzo, V. Kabanets & I. Volkovich (2018). The Power of Natural Properties as Oracles. In 33rd Computational Complexity Conference CCC, 7:1–7:20. URL https://doi.org/10.4230/LIPIcs.CCC.2018.7.

  • R. Impagliazzo, V. Kabanets & A. Wigderson (2002). In search of an easy witness: exponential time vs. probabilistic polynomial time. J. of Computer and System Sciences 65(4), 672–694.

  • R. Impagliazzo & A. Wigderson (1997). P=BPP unless E has subexponential circuits: derandomizing the XOR lemma. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 220–229.

  • R. Impagliazzo & A. Wigderson (1998). Randomness vs. Time: De-Randomization under a Uniform Assumption. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 734–743.

  • A. Jain, H. Lin & A. Sahai (2021). Indistinguishability obfuscation from well-founded assumptions. In 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC, 60–73. ACM. URL https://doi.org/10.1145/3406325.3451093.

  • V. Kabanets & J. Cai (2000). Circuit minimization problem. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), 73–79.

  • R. M. Karp (1985). Turing award lecture. In Proceedings of the 1985 ACM annual conference on The range of computing: mid-80’s perspective: mid-80’s perspective, Denver, Colorado, USA, October 14-16, 1985, 193.

  • R. M. Karp & R. J. Lipton (1980). 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, 302–309. URL http://doi.acm.org/10.1145/800141.804678.

  • A. Klivans, P. Kothari & I. Oliveira (2013). Constructing Hard Functions from Learning Algorithms. In Proceedings of the 28th Annual IEEE Conference on Computational Complexity (CCC), 86–97.

  • Adam Klivans & Dieter van Melkebeek (2002). Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial- Time Hierarchy Collapses. SIAM J. Comput. 31(5), 1501–1526. URL http://dx.doi.org/10.1137/S0097539700389652.

  • J. Köbler & O. Watanabe (1998). New Collapse Consequences of NP Having Small Circuits. SIAM J. Comput. 28(1), 311–324.

  • C. Lund, L. Fortnow, H. Karloff & N. Nisan (1992). Algebraic methods for interactive proof systems. JACM 39(4), 859–868.

  • D. van Melkebeek & K. Pervyshev (2007). A Generic Time Hierarchy with One Bit of Advice. Computational Complexity 16(2), 139–179.

  • C. D. Murray & R. R. Williams (2015). On the (Non) NP-Hardness of Computing Circuit Complexity. In 30th Conference on Computational Complexity, CCC, 365–380. URL http://dx.doi.org/10.4230/LIPIcs.CCC.2015.365.

  • N. Nisan & A. Wigderson (1994). Hardness vs. randomness. J. Comput. Syst. Sci. 49(2), 149–167. ISSN 0022-0000.

  • I. C. Oliveira & R. Santhanam (2017). Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. In 32nd Computational Complexity Conference, CCC, 18:1–18:49.

  • A. A. Razborov & S. Rudich (1997). Natural Proofs. J. of Computer and System Sciences 55(1), 24–35.

  • M. Saks & R. Santhanam (2020). Circuit Lower Bounds from NPHardness of MCSP Under Turing Reductions. In 35th Computational Complexity Conference, CCC, 26:1–26:13.

  • R. Santhanam (2009). Circuit Lower Bounds for Merlin–Arthur Classes. SIAM J. Comput. 39(3), 1038–1061.

  • S. Toda (1991). PP is as hard as the polynomial time hierarchy. SIAM J. on Computing 20(5), 865–877.

  • B. A. Trakhtenbrot (1984). A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms. IEEE Annals of the History of Computing 6(4), 384–400.

  • L. Trevisan & S. P. Vadhan (2007). Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity 16(4), 331–364.

  • C. Umans (2003). Pseudo-random generators for all hardnesses. J. of Computer and System Sciences 67(2), 419–440.

  • L. G. Valiant (1979). The complexity of computing the permanent. Theoretical Computer Science 8(2), 189–201. ISSN 0304-3975.

  • L. G. Valiant (1984). A theory of the learnable. Communications of the ACM 27(11), 1134–1142.

  • I. Volkovich (2014). On Learning, Lower Bounds and (un)Keeping Promises. In Proceedings of the 41st ICALP, 1027–1038.

Download references

Acknowledgements

We thank Eric Allender and Scott Aaronson for answering our questions and many useful conversations. We also thank the anonymous referees for their useful comments.

An extended abstract of this paper has appeared as Impagliazzo et al. (2018).

Author information

Authors and Affiliations

  1. Department of Computer Science, University of California San Diego, La Jolla, CA, USA

    Russell Impagliazzo

  2. School of Computing Science, Simon Fraser University, Burnaby, BC, Canada

    Valentine Kabanets

  3. Computer Science Department, Boston College, Chestnut Hill, MA, USA

    Ilya Volkovich

Authors
  1. Russell Impagliazzo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Valentine Kabanets
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ilya Volkovich
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ilya Volkovich.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Impagliazzo, R., Kabanets, V. & Volkovich, I. The Power of Natural Properties as Oracles. comput. complex. 32, 6 (2023). https://doi.org/10.1007/s00037-023-00241-0

Download citation

  • Received:

  • Published:

  • DOI: https://doi.org/10.1007/s00037-023-00241-0

keywords

Subject classification

Search

Navigation