Immunity and simplicity in relativizations of probabilistic complexity classes
José L. Balcázar, David A. Russo · RAIRO - Theoretical Informatics and Applications · 1988
The existence of immune and simple sets in relativizations of the probabilistic polynomial time bounded classes is studied. Some techniques previously used to show similar results for relativizations of P and NP are adapted to the probabilistic classes. Using these results, an exhaustive settling of all possible strong separations among these relativized classes is obtained.