Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Polynomial-Time Random Oracles and Separating Complexity Classes

Polynomial-Time Random Oracles and Separating Complexity Classes Bennett and Gill [1981] showed that PA NPA coNPA for a random oracle A, with probability 1. We investigate whether this result extends to individual polynomial-time random oracles. We consider two notions of random oracles: p-random oracles in the sense of martingales and resource-bounded measure [Lutz 1992; Ambos-Spies et al. 1997], and p-betting-game random oracles using the betting games generalization of resource-bounded measure [Buhrman et al. 2000]. Every p-betting-game random oracle is also p-random; whether the two notions are equivalent is an open problem. (1) We first show that PA NPA for every oracle A that is p-betting-game random. Ideally, we would extend (1) to p-random oracles. We show that answering this either way would imply an unrelativized complexity class separation: (2) If PA NPA relative to every p-random oracle A, then BPP EXP. (3) If PA NPA relative to some p-random oracle A, then P PSPACE. Rossman, Servedio, and Tan [2015] showed that the polynomial-time hierarchy is infinite relative to a random oracle, solving a longstanding open problem. We consider whether we can extend (1) to show that PHA is infinite relative to oracles A that are p-betting-game random. Showing that PHA separates at even its first level would also imply an unrelativized complexity class separation: (4) If NPA coNPA for a p-betting-game measure 1 class of oracles A, then NP EXP. (5) If PHA is infinite relative to every p-random oracle A, then PH EXP. We also consider random oracles for time versus space, for example: (6) LA PA relative to every oracle A that is p-betting-game random. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Polynomial-Time Random Oracles and Separating Complexity Classes

Download PDF
16 pages

Loading next page...
 
/lp/association-for-computing-machinery/polynomial-time-random-oracles-and-separating-complexity-classes-TypO405A5L
Publisher
Association for Computing Machinery
Copyright
Copyright © 2021 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3434389
Publisher site
See Article on Publisher Site

Abstract

Bennett and Gill [1981] showed that PA NPA coNPA for a random oracle A, with probability 1. We investigate whether this result extends to individual polynomial-time random oracles. We consider two notions of random oracles: p-random oracles in the sense of martingales and resource-bounded measure [Lutz 1992; Ambos-Spies et al. 1997], and p-betting-game random oracles using the betting games generalization of resource-bounded measure [Buhrman et al. 2000]. Every p-betting-game random oracle is also p-random; whether the two notions are equivalent is an open problem. (1) We first show that PA NPA for every oracle A that is p-betting-game random. Ideally, we would extend (1) to p-random oracles. We show that answering this either way would imply an unrelativized complexity class separation: (2) If PA NPA relative to every p-random oracle A, then BPP EXP. (3) If PA NPA relative to some p-random oracle A, then P PSPACE. Rossman, Servedio, and Tan [2015] showed that the polynomial-time hierarchy is infinite relative to a random oracle, solving a longstanding open problem. We consider whether we can extend (1) to show that PHA is infinite relative to oracles A that are p-betting-game random. Showing that PHA separates at even its first level would also imply an unrelativized complexity class separation: (4) If NPA coNPA for a p-betting-game measure 1 class of oracles A, then NP EXP. (5) If PHA is infinite relative to every p-random oracle A, then PH EXP. We also consider random oracles for time versus space, for example: (6) LA PA relative to every oracle A that is p-betting-game random.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Jan 21, 2021

Keywords: Random oracles

References

  • Measure on small complexity classes with applications for BPP
    Allender, E.; Strauss, M.
  • Resource-bounded measure and randomness
    Ambos-Spies, K.; Mayordomo, E.
  • Random oracles separate PSPACE from the polynomial-time hierarchy
    Babai, L.
  • On the relativized power of additional accepting paths
    Beigel, R.
  • Relative to a random oracle A, PA ≠ NPA ≠ co-NPA with Probability 1
    Bennett, C. H.; Gill, J.
  • Tally languages and complexity classes
    Book, R. V.
  • An observation on probability versus randomness with applications to complexity classes
    Book, R. V.; Lutz, J. H.; Wagner, K. W.
  • A generalization of resource-bounded measure, with application to the BPP vs
    Buhrman, H.; van Melkebeek, D.; Regan, K. W.; Sivakumar, D.; Strauss, M.
  • With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
    Cai, J.
  • The random oracle hypothesis is false
    Chang, R.; Chor, B.; Goldreich, O.; Hartmanis, J.; Håstad, J.; Ranjan, D.; Rohatgi, R.
  • Exact learning algorithms, betting games, and circuit lower bounds
    Harkins, R. C.; Hitchcock, J. M.
  • Computational Limitations for Small-Depth Circuits
    Håstad, J.
  • Hausdorff dimension and oracle constructions
    Hitchcock, J. M.
  • The fractal geometry of complexity classes
    Hitchcock, J. M.; Lutz, J. H.; Mayordomo, E.
  • Weak completeness in E and E2
    Juedes, D. W.; Lutz, J. H.
  • Almost everywhere high nonuniform complexity
    Lutz, J. H.
  • The quantitative structure of exponential time
    Lutz, J. H.
  • Circuit size relative to pseudorandom oracles
    Lutz, J. H.; Schmidt, W. J.
  • The definition of random sequences
    Martin-Löf, P.
  • Kolmogorov-Loveland randomness and stochasticity
    Merkle, W.; Miller, J. S.; Nies, A.; Reimann, J.; Stephan, F.
  • Mathematical metaphysics of randomness
    Muchnik, A. A.; Semenov, A. L.; Uspensky, V. A.
  • Hardness vs
    Nisan, N.; Wigderson, A.
  • An average-case depth hierarchy theorem for Boolean circuits
    Rossman, B.; Servedio, R. A.; Tan, L.-Y.