## 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.

(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.

Original language | English |
---|---|

Article number | 1 |

Number of pages | 16 |

Journal | ACM Transactions on Computation Theory |

Volume | 13 |

Issue number | 1 |

Early online date | 21 Jan 2021 |

DOIs | |

Publication status | Published - 1 Mar 2021 |

Externally published | Yes |