[39] Show that if A is a set whose characteristic sequence is a random infinite binary sequence in the sense of Martin-L¨of (Section 2.5), then PA = NPA.

Comments. This result is presented in a more general setting using results of Section 2.5 by R.V. Book, J.H. Lutz, and K.W. Wagner in [Math.

Systems Theory, 27(1994), 201–209]. Such a set A can be used to establish other known probability-one oracle separations such as PHA = PSPACEA, where PH is the polynomial hierarchy. See also [R.V. Book and O. Watanabe, Inform. Comput., 125(1996), 70–76]. Source: [C.H.
Bennett and J. Gill, SIAM J. Comput., 10:1(1981), 96–113].