[35] Call a probability distribution P : N→R malign for a class of algorithms if each algorithm in the class runs in P-average time

(space) equal to worst-case time (space). In Section 4.4 it was shown that m is malign for the computable algorithms. As usual P∗



(x) =

y≤x P(y) and the function P∗ is computable in time t if there exists a t(n)-time-bounded Turing machine that on input x, 1k writes the truncated binary expansion y of P(x) such that |P∗(x) − y| ≤ 1/2k.

(a) Show that for every total computable function f there exists a probability distribution P that is malign for the class of f-time bounded algorithms, and P∗ is computable in polynomial time.

Define a probability ensemble as the set of probability distributions {Pn}

defined by Pn(x) = P(x|l(x) = n). It is polynomial-time computable if each P∗

n is polynomial-time computable. Similarly for exponential time.

(b) Show that there exists an exponential-time computable probability ensemble that is malign for the class of polynomial-time algorithms.

(c) Show that there does not exist a polynomial-time computable probability ensemble that is malign for the class of polynomial-time algorithms.
Comments. Source: [P.B. Miltersen, SIAM J. Comput., 22:1(1993), 147–
156]. This contains many more results on malignness. K. Kobayashi studied the differences and relations between malign measures and universal distributions in classes of distributions in [IEICE Trans. Inform. Systems, E76-D:6(1993), 634–640; Theoret. Comput. Sci., 181(1997), 289–
306]. A. Jakoby, R. Reischuk, and C. Schindelhauer studied malign distributions for average-case circuit complexity in [Inform. Comput., 150(1999), 187–208].