Immunity, simplicity, probabilistic complexity classes and relativizations
Hongzhou Li · International Journal of Computer Mathematics · 1988
Let R be random polynomial-time complexity class and UP be the class of sets accepted by polynomial-time NTMs which have an unique accepting path for each string they accept. Let R(A) be the relativization of these classes with respect to oracle A. Similarly, we define co-NP(A)NP(A)UP(A)P(A), and co-R(A). In this paper, we prove the following main results: 1. There exists a recursive oracle set A such that R(A) contains a P(A)-immune set. 2. There exists a recursive oracle set B such that R(B) contains a P(B)-immune set and NP(B) = R(B). 3. There exists an oracle set C such that NP(C) contains a R(C)-immune set and R(C) = P(C). 4. There exists a resursive oracle set D such that R(D) contains a simple set and NP(D) = R(D). We have the similar results for UP and ZPP = R ∩ co-R.