(a) [35] Improve Theorem 7.3.6 by proving BPPR

= PR

, where R = {x : C(x) ≥ l(x)/i} for i a positive integer.

(b) [33] Show that PSPACE ⊆ PR and NEXP ⊆ NPR, with R as in Theorem 7.3.6.

(c) [O38]) Is there a larger complexity class DTIME(t), NTIME(t), or DSPACE(s), for some t or s, that is contained in PR?

Comments. Source for Items

(a) and (b): [E. Allender, H.M. Buhrman, M. Kouck´y, D. van Melkebeek, and D. Ronneburger, SIAM J. Comput., 35:6(2006), 14671493]. Hint for Item (a): use the pseudorandom generators of R. Impagliazzo and A. Wigderson [Proc. 38th IEEE Symp.

Found. Comp. Sci., 1997, 220–229]. Item

(c) is from E. Allender, email of March 18, 2006.