Relativized Questions Involving Probabilistic Algorithms
Charles Rackoff · Journal of the ACM · 1982
Let R _ NP be the collecUon of languages L such that for some polynomial-time-computable predicate P(x, y) and constant k, L = (xl3y , lYl = Ix:, P(x, y)) = (x13 at least 2 Ix:-1 values of y, lYl = Ixl k, P(x, y)) Let U _ NP be the collecuon of languages L such that for some polynomial-time-computable predicate P(x, y) and constant k, Z = (xl3y, lYl = Ixl k, e(x, .v))= {xlB umque y, lYl = Ixl', e(x, y)) Let R A, U A, pA, NpA, and CO-NP a be the relatwlzatton of these classes with respect to an oracle A Then for some oracles E and F, (NP E tq CO-NP E) = R e = pE ~ Npe and (NP r tq CO-NP F) ffi U F = pF ~ NpF, while for some other oracle D, CO.NPO=Npo= U o = R o ~ Po