Polynomial-Time Random Oracles and Separating Complexity Classes

John M. Hitchcock, Adewale Sekoni, and Hadi Shafei

Abstract:
Bennett and Gill (1981) showed that P^A ≠ NP^A ≠ coNP^A 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.

We first show that P^A ≠ NP^A 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:

If P^A ≠ NP^A relative to every p-random oracle A, then BPP ≠ EXP.
If P^A = NP^A 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 PH^A is infinite relative to oracles A that are p-betting-game random. Showing that PH^A separates at even its first level would also imply an unrelativized complexity class separation:

If NP^A ≠ coNP^A for a p-betting-game measure 1 class of oracles A, then NP ≠ EXP.
If PH^A is infinite relative to every p-random oracle A, then PH ≠ EXP.

We also consider random oracles for time versus space, for example:

LOGSPACE^A ≠ P^A relative to every oracle A that is p-betting-game random.

Journal version:

ACM Transactions on Computation Theory, 13(1), article 1, 2021.
[pdf]

Technical reports:

Technical Report TR18-018, Electronic Colloquium on Computational Complexity, 2018.
Technical Report arXiv:1801.07317, 2018.