Separations with Immunity Relative to a Random Oracle in Computational Complexity

Abstract

Rossman, Servedio, and Tan proved that the polynomial hierarchy is infinite relative to a random oracle. This paper strengthens this celebrated result by considering \emph{strong separations}, witnessed by immune languages. The main result of the paper shows that with respect to a random oracle the levels of the polynomial hierarchy separate with immunity. Specifically, with probability one over a random oracle $A$, for every $k\ge 1$ there is a language in ${\Sigma }_k^{P,A}$ that is immune to ${\Pi }_k^{P,A}$, and, symmetrically, a language in ${\Pi }_k^{P,A}$ that is immune to ${\Sigma }_k^{P,A}$. We thus extend classical results due to Bennett and Gill and Vereshchagin. We accomplish this by developing a "rare-or-wrong" approach to strong separations. We highlight the flexibility of the approach by strengthening other separations with respect to a random oracle from the complexity-theoretic literature.