Random oracles show stronger layered computational complexity separations
Separations with Immunity Relative to a Random Oracle in Computational Complexity
Computational Complexity
Summary
The authors improve our understanding of the complexity of computational problems when assuming a random oracle, a kind of black box that provides random answers. They show that different levels of the polynomial hierarchy—a way of organizing problems by difficulty—are not only separate but strongly so, by proving the existence of special hard problems called immune languages at each level. This strengthens previous work by showing these separations hold with high certainty under randomness. They also develop a new method called the "rare-or-wrong" approach to prove these strong separations.
What this means in practice
- •For complexity theorists: Guide the design of complexity class separations using immunity to establish stronger hierarchy results.
- •For algorithm designers: Inform the limits of algorithmic approaches when oracle-based separations indicate inherent problem hardness structures.
A theory result. No direct application yet.
Authors
Gabriel Istrate
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\geq 1$ there is a language in $Σ_{k}^{P,A}$ that is immune to $Π_{k}^{P,A}$, and, symmetrically, a language in $Π_{k}^{P,A}$ that is immune to $Σ_{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.