Document Open Access Logo

Bounded Relativization

Authors Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

PDF
Thumbnail PDF

File

LIPIcs.CCC.2023.6.pdf
  • Filesize: 1.22 MB
  • 45 pages

Document Identifiers

Author Details

Shuichi Hirahara
  • National Institute of Informatics, Tokyo, Japan
Zhenjian Lu
  • University of Oxford, UK
Hanlin Ren
  • University of Oxford, UK

Funding

  • Hirahara, Shuichi: Supported by JST, PRESTO Grant Number JPMJPR2024, Japan.
  • Ren, Hanlin: Received support from DIMACS through grant number CCF-1836666 from the National Science Foundation.

Acknowledgements

We thank Rahul Santhanam for helpful discussions and for pointing out that the oracle in Theorem 52 can be constructed in EXPH, using [Shafi Goldwasser et al., 2021] only as a black-box. We thank Lijie Chen for helpful discussions regarding [Lijie Chen et al., 2022], Ian Mertz for discussions about the statement ({*}), and Ryan Williams for useful discussions about time-space tradeoffs for SAT. We thank Lijie Chen (again) and an anonymous CCC reviewer for pointing out an error in a previous version of this paper. Part of this work was completed when the authors are visiting the Simons Institute for the Theory of Computing, participating in the Meta-Complexity program.

Cite As Get BibTex

Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren. Bounded Relativization. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 6:1-6:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CCC.2023.6

Abstract

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called bounded relativization. For a complexity class ℭ, we say that a statement is ℭ-relativizing if the statement holds relative to every oracle 𝒪 ∈ ℭ. It is easy to see that every result that relativizes also ℭ-relativizes for every complexity class ℭ. On the other hand, we observe that many non-relativizing results, such as IP = PSPACE, are in fact PSPACE-relativizing.
First, we use the idea of bounded relativization to obtain new lower bound results, including the following nearly maximum circuit lower bound: for every constant ε > 0, BPE^{MCSP}/2^{εn} ⊈ SIZE[2ⁿ/n]. 
We prove this by PSPACE-relativizing the recent pseudodeterministic pseudorandom generator by Lu, Oliveira, and Santhanam (STOC 2021).
Next, we study the limitations of PSPACE-relativizing proof techniques, and show that a seemingly minor improvement over the known results using PSPACE-relativizing techniques would imply a breakthrough separation NP ≠ L. For example:  
- Impagliazzo and Wigderson (JCSS 2001) proved that if EXP ≠ BPP, then BPP admits infinitely-often subexponential-time heuristic derandomization. We show that their result is PSPACE-relativizing, and that improving it to worst-case derandomization using PSPACE-relativizing techniques implies NP ≠ L.
- Oliveira and Santhanam (STOC 2017) recently proved that every dense subset in P admits an infinitely-often subexponential-time pseudodeterministic construction, which we observe is PSPACE-relativizing. Improving this to almost-everywhere (pseudodeterministic) or (infinitely-often) deterministic constructions by PSPACE-relativizing techniques implies NP ≠ L.
- Santhanam (SICOMP 2009) proved that pr-MA does not have fixed polynomial-size circuits. This lower bound can be shown PSPACE-relativizing, and we show that improving it to an almost-everywhere lower bound using PSPACE-relativizing techniques implies NP ≠ L.
In fact, we show that if we can use PSPACE-relativizing techniques to obtain the above-mentioned improvements, then PSPACE ≠ EXPH. We obtain our barrier results by constructing suitable oracles computable in EXPH relative to which these improvements are impossible.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Oracles and decision trees
  • Theory of computation → Circuit complexity
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • relativization
  • circuit lower bound
  • derandomization
  • explicit construction
  • pseudodeterministic algorithms
  • interactive proofs

Metrics

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

Related Versions

References

  1. Scott Aaronson. Oracles are subtle but not malicious. In Conference on Computational Complexity (CCC), pages 340-354. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/CCC.2006.32.
  2. Scott Aaronson. The teaser. https://scottaaronson.blog/?p=3054, 2017. Accessed: Feb 6, 2023.
  3. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):2:1-2:54, 2009. URL: https://doi.org/10.1145/1490270.1490272.
  4. Eric Allender. Oracles versus proof techniques that do not relativize. In SIGAL International Symposium on Algorithms, volume 450 of Lecture Notes in Computer Science, pages 39-52. Springer, 1990. URL: https://doi.org/10.1007/3-540-52921-7_54.
  5. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM J. Comput., 35(6):1467-1493, 2006. URL: https://doi.org/10.1137/050628994.
  6. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  7. Sanjeev Arora, Russell Impagliazzo, and Umesh Vazirani. Relativizing versus nonrelativizing techniques: the role of local checkability. Manuscript, 1992. URL: https://people.eecs.berkeley.edu/~vazirani/pubs/relativizing.pdf.
  8. Barış Aydınlıoğlu and Eric Bach. Affine relativization: Unifying the algebrization and relativization barriers. ACM Trans. Comput. Theory, 10(1):1:1-1:67, 2018. URL: https://doi.org/10.1145/3170704.
  9. László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex., 1:3-40, 1991. URL: https://doi.org/10.1007/BF01200056.
  10. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307-318, 1993. URL: https://doi.org/10.1007/BF01275486.
  11. Theodore P. Baker, John Gill, and Robert Solovay. Relativizations of the P = ? NP question. SIAM J. Comput., 4(4):431-442, 1975. URL: https://doi.org/10.1137/0204037.
  12. Harry Buhrman, Lance Fortnow, and Rahul Santhanam. Unconditional lower bounds against advice. In International Colloquium on Automata, Languages and Programming (ICALP), pages 195-209, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_18.
  13. Harry Buhrman, Lance Fortnow, and Thomas Thierauf. Nonrelativizing separations. In Conference on Computational Complexity (CCC), pages 8-12, 1998. URL: https://doi.org/10.1109/CCC.1998.694585.
  14. Harry Buhrman and Leen Torenvliet. Randomness is hard. SIAM J. Comput., 30(5):1485-1501, 2000. URL: https://doi.org/10.1137/S0097539799360148.
  15. Samuel R. Buss and R. Ryan Williams. Limits on alternation trading proofs for time-space lower bounds. Comput. Complex., 24(3):533-600, 2015. URL: https://doi.org/10.1007/s00037-015-0104-9.
  16. Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false. J. Comput. Syst. Sci., 49(1):24-39, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80084-4.
  17. Lijie Chen, Xin Lyu, and R. Ryan Williams. Almost-everywhere circuit lower bounds from non-trivial derandomization. In Symposium on Foundations of Computer Science (FOCS), pages 1-12. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00009.
  18. Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Relations and equivalences between circuit lower bounds and Karp-Lipton theorems. In Computational Complexity Conference (CCC), volume 137 of LIPIcs, pages 30:1-30:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.30.
  19. Lijie Chen, Ron D. Rothblum, and Roei Tell. Unstructured hardness to average-case randomness. In Symposium on Foundations of Computer Science (FOCS), pages 429-437. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00048.
  20. Lijie Chen, Ron D. Rothblum, Roei Tell, and Eylon Yogev. On exponential-time hypotheses, derandomization, and circuit lower bounds. In Symposium on Foundations of Computer Science (FOCS), pages 13-23. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00010.
  21. Lijie Chen and Roei Tell. Hardness vs randomness, revised: Uniform, non-black-box, and instance-wise. In Symposium on Foundations of Computer Science (FOCS), pages 125-136. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00021.
  22. Scott Diehl and Dieter van Melkebeek. Time-space lower bounds for the polynomial-time hierarchy on randomized machines. SIAM J. Comput., 36(3):563-594, 2006. URL: https://doi.org/10.1137/050642228.
  23. Lance Fortnow. The role of relativization in complexity theory. Bull. EATCS, 52:229-243, 1994. Google Scholar
  24. Lance Fortnow. Time-space tradeoffs for satisfiability. J. Comput. Syst. Sci., 60(2):337-353, 2000. URL: https://doi.org/10.1006/jcss.1999.1671.
  25. Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, and Anastasios Viglas. Time-space lower bounds for satisfiability. J. ACM, 52(6):835-865, 2005. URL: https://doi.org/10.1145/1101821.1101822.
  26. Lance Fortnow and Rahul Santhanam. Hierarchy theorems for probabilistic polynomial time. In Symposium on Foundations of Computer Science (FOCS), pages 316-324, 2004. URL: https://doi.org/10.1109/FOCS.2004.33.
  27. Lance Fortnow, Rahul Santhanam, and R. Ryan Williams. Fixed-polynomial size circuit bounds. In Computational Complexity Conference (CCC), pages 19-26. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/CCC.2009.21.
  28. Lance Fortnow and Michael Sipser. Are there interactive protocols for coNP languages? Inf. Process. Lett., 28(5):249-251, 1988. URL: https://doi.org/10.1016/0020-0190(88)90199-8.
  29. Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing bounds on the circuit size of the hardest functions. Inf. Process. Lett., 95(2):354-357, 2005. URL: https://doi.org/10.1016/j.ipl.2005.03.009.
  30. Oded Goldreich. Computational complexity - A conceptual perspective. Cambridge University Press, 2008. Google Scholar
  31. Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam. On the pseudo-deterministic query complexity of NP search problems. In Computational Complexity Conference (CCC), volume 200 of LIPIcs, pages 36:1-36:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.36.
  32. Hans Heller. On relativized exponential and probabilistic complexity classes. Inf. Control., 71(3):231-243, 1986. URL: https://doi.org/10.1016/S0019-9958(86)80012-2.
  33. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within NP. In Symposium on Foundations of Computer Science (FOCS), pages 247-258, 2018. URL: https://doi.org/10.1109/FOCS.2018.00032.
  34. Shuichi Hirahara. Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions. In Computational Complexity Conference (CCC), volume 169 of LIPIcs, pages 20:1-20:47. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.20.
  35. Shuichi Hirahara. Unexpected hardness results for Kolmogorov complexity under uniform reductions. In Symposium on Theory of Computing (STOC), pages 1038-1051, 2020. URL: https://doi.org/10.1145/3357713.3384251.
  36. Shuichi Hirahara. Symmetry of information from meta-complexity. In Computational Complexity Conference (CCC), volume 234 of LIPIcs, pages 26:1-26:41. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.CCC.2022.26.
  37. Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren. Bounded relativization. Electron. Colloquium Comput. Complex., 30:70, 2023. URL: https://eccc.weizmann.ac.il/report/2023/070.
  38. Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. An axiomatic approach to algebrization. In Symposium on Theory of Computing (STOC), pages 695-704. ACM, 2009. URL: https://doi.org/10.1145/1536414.1536509.
  39. Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. The power of natural properties as oracles. In Computational Complexity Conference (CCC), volume 102 of LIPIcs, pages 7:1-7:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.7.
  40. 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.
  41. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Symposium on Theory of Computing (STOC), pages 220-229. ACM, 1997. URL: https://doi.org/10.1145/258533.258590.
  42. Russell Impagliazzo and Avi Wigderson. Randomness vs time: Derandomization under a uniform assumption. J. Comput. Syst. Sci., 63(4):672-688, 2001. URL: https://doi.org/10.1006/jcss.2001.1780.
  43. Emil Jerábek. Dual weak pigeonhole principle, Boolean complexity, and derandomization. Ann. Pure Appl. Log., 129(1-3):1-37, 2004. URL: https://doi.org/10.1016/j.apal.2003.12.003.
  44. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP^* = RE. CoRR, abs/2001.04383, 2020. URL: https://doi.org/10.48550/arXiv.2001.04383.
  45. Valentine Kabanets. Easiness assumptions and hardness tests: Trading time for zero error. J. Comput. Syst. Sci., 63(2):236-252, 2001. URL: https://doi.org/10.1006/jcss.2001.1763.
  46. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Symposium on Theory of Computing (STOC), pages 73-79. ACM, 2000. URL: https://doi.org/10.1145/335305.335314.
  47. Ravi Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Inf. Control., 55(1-3):40-56, 1982. URL: https://doi.org/10.1016/S0019-9958(82)90382-5.
  48. Richard M. Karp and Richard J. Lipton. Some connections between nonuniform and uniform complexity classes. In Symposium on Theory of Computing (STOC), pages 302-309. ACM, 1980. URL: https://doi.org/10.1145/800141.804678.
  49. Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos H. Papadimitriou. Total functions in the polynomial hierarchy. In Innovations in Theoretical Computer Science (ITCS), volume 185 of LIPIcs, pages 44:1-44:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.44.
  50. Adam R. Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501-1526, 2002. URL: https://doi.org/10.1137/S0097539700389652.
  51. Oliver Korten. The hardest explicit construction. In Symposium on Foundations of Computer Science (FOCS), pages 433-444. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00051.
  52. Leonid A. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61(1):15-37, 1984. URL: https://doi.org/10.1016/S0019-9958(84)80060-1.
  53. Richard J. Lipton and Anastasios Viglas. On the complexity of SAT. In Symposium on Foundations of Computer Science (FOCS), pages 459-464. IEEE Computer Society, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814618.
  54. Zhenjian Lu, Igor Carboni Oliveira, and Rahul Santhanam. Pseudodeterministic algorithms and the structure of probabilistic time. In Symposium on Theory of Computing (STOC), pages 303-316. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451085.
  55. 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.
  56. Oleg B Lupanov. On the synthesis of switching circuits. Doklady Akademii Nauk SSSR, 119(1):23-26, 1958. Google Scholar
  57. Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe. Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In International Computing and Combinatorics Conference (COCOON), pages 210-220, 1999. URL: https://doi.org/10.1007/3-540-48686-0_21.
  58. Cody D. Murray and R. Ryan Williams. Easiness amplification and uniform circuit lower bounds. In Computational Complexity Conference (CCC), volume 79 of LIPIcs, pages 8:1-8:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.8.
  59. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  60. Igor C. Oliveira. Randomness and intractability in Kolmogorov complexity. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 32:1-32:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.32.
  61. Igor C. Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Computational Complexity Conference (CCC), pages 18:1-18:49, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.18.
  62. Igor C. Oliveira and Rahul Santhanam. Pseudodeterministic constructions in subexponential time. In Symposium on Theory of Computing (STOC), pages 665-677, 2017. URL: https://doi.org/10.1145/3055399.3055500.
  63. Hanlin Ren and Rahul Santhanam. A relativization perspective on meta-complexity. In International Symposium on Theoretical Aspects of Computer Science (STACS), volume 219 of LIPIcs, pages 54:1-54:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.STACS.2022.54.
  64. Hanlin Ren, Rahul Santhanam, and Zhikun Wang. On the range avoidance problem for circuits. In FOCS, pages 640-650. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00067.
  65. Rahul Santhanam. Circuit lower bounds for Merlin-Arthur classes. SIAM J. Comput., 39(3):1038-1061, 2009. URL: https://doi.org/10.1137/070702680.
  66. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, 1992. URL: https://doi.org/10.1145/146585.146609.
  67. Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell Syst. Tech. J., 28(1):59-98, 1949. URL: https://doi.org/10.1002/j.1538-7305.1949.tb03624.x.
  68. Michael Sipser. A complexity theoretic approach to randomness. In Symposium on Theory of Computing (STOC), pages 330-335, 1983. URL: https://doi.org/10.1145/800061.808762.
  69. Larry J. Stockmeyer. The complexity of approximate counting (preliminary version). In Symposium on Theory of Computing (STOC), pages 118-126. ACM, 1983. URL: https://doi.org/10.1145/800061.808740.
  70. 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.
  71. 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.
  72. Salil P. Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  73. 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.
  74. Emanuele Viola. On approximate majority and probabilistic time. In Conference on Computational Complexity (CCC), pages 155-168. IEEE Computer Society, 2007. URL: https://doi.org/10.1109/CCC.2007.16.
  75. Nikhil Vyas and R. Ryan Williams. On oracles and algorithmic methods for proving lower bounds. In Innovations in Theoretical Computer Science Conference (ITCS), volume 251 of LIPIcs, pages 99:1-99:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.ITCS.2023.99.
  76. R. Ryan Williams. Inductive time-space lower bounds for SAT and related problems. Comput. Complex., 15(4):433-470, 2006. URL: https://doi.org/10.1007/s00037-007-0221-1.
  77. R. Ryan Williams. Time-space tradeoffs for counting NP solutions modulo integers. Comput. Complex., 17(2):179-219, 2008. URL: https://doi.org/10.1007/s00037-008-0248-y.
  78. R. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218-1244, 2013. URL: https://doi.org/10.1137/10080703X.
  79. R. Ryan Williams. Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2:1-2:32, 2014. URL: https://doi.org/10.1145/2559903.
  80. Christopher B. Wilson. Relativized circuit complexity. J. Comput. Syst. Sci., 31(2):169-181, 1985. URL: https://doi.org/10.1016/0022-0000(85)90040-6.
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact