Seeking Stronger Separations: Probability One Balanced- and Bi-Immunity

摘要

We prove that NP and +(in circle)P are P balanced immune relative to a randomoracle. Such a result is unobtainable for NT, as we prove that NT is not P balanced immune (and this result itself relativizes). However, we prove that NT is P bi-immune relative to a random oracle. We note also that UP and coUP differ relative to a random oracle.