@misc {IOPORT.03995648,
    author       = {Ambos-Spies, Klaus},
    title        = {Randomness, relativizations, and polynomial reducibilities.},
    howpublished = {Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 23-34 (1986).},
    year         = {1986},
    abstract     = {[For the entire collection see Zbl 0591.00015.] The author considers the following two polynomial reducibilities: p-many- one (pm), and p-Turing (pT) reducibility. He proves that for every set A not in P the class of sets which are pm-incomparable with A has measure 1. As a matter of fact, for a randomly chosen set B, A and B almost surely form a minimal pair with respect to pm-reducibility. Let BPP be the class of problems recognized by probabilistic polynomial time bounded Turing machines with error probability uniformly bounded below 1/2. Then for every A not in BPP the class of sets which are pT-incomparable with A has measure 1. Further applications are related to the question whether BPP has complete problems. {\it C. H. Bennett} and {\it J. Gill} [SIAM J. Comput. 10, 96-113 (1981; Zbl 0454.68030)] proved that for a random oracle A, $P(A)=BPP(A)$ with probability 1. In the final section the author proves that this is a best possible result: indeed, for every class C, if C(A)$\subseteq BPP(A)$ with probability 1, then $C\subseteq BPP$.},
    reviewer     = {D.Mundici},
    identifier   = {03995648},
}