Access the full text.
Sign up today, get DeepDyve free for 14 days.
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.
ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery
Published: Jan 21, 2021
Keywords: Random oracles
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.