[36] A probability mass function P is P-computable if it satisfies Definition 7.6.1 with the time t(n) a polynomial in n. A probability mass function P is P-samplable if there is a probabilistic Turing machine T that on input k computes a string x such that |Pr(T (k) = x) −

P(x)| ≤ 1/2k and T runs in time polynomial in l(x) + k. Clearly, every P-computable probability mass function is P-samplable.

(a) Show that if one-way functions exist then there is a P-samplable probability mass function that is not multiplicatively dominated by a P-computable one.

(b) Let P be a P-samplable probability mass function. For every polynomial p, there is a P-samplable probability mass function P such that mp(x) ≤ P(x)/p(x).

(c) Let P be a P-samplable probability mass function. Show that under a reasonable derandomization assumption, for some polynomial p, mp(x) ≥ P(x)/p(x).

(d) Show that if there exists a P-computable probability mass function P such that mt

(x) = O(P(x)), for some t, then pseudorandom generators do not exist.

Comments. Existence of one-way functions also figures in Exercise 7.1.12 on page 564. Source for Item (a): [S. Ben-David, B. Chor, O. Goldreich, and M. Luby, 20th ACM Symp. Theory Comput., 1989, 204–216];

Item (b): [L. Antunes, L. Fortnow, D. van Melkebeek, and N.V. Vinodchandran Theoret. Comput. Sci., 354(2006), 391–404]; Item (c): [L.
Antunes and L. Fortnow, Electr. Coll. Comput. Complexity, 144(2005)];
Item (d): [R. Schuler [16th Symp. Theoret. Aspects Comput. Sci., 1999, pp. 434–443; 12th IEEE Conf. Comput. Complexity 1997, pp. 69–73].