Page 220

		9-2 This exercise establishes that the tradeoff established in Exercise 9-1 is optimal. For each r, , define

		Show the following:

		(a) for all k, , where .

		(b) . Hint: Use a priority construction.

		9-3 Show that if and only if (i) and (ii) b = * or .

		9-4 Show that: .

		9-5 (Pitt [149, 150]) Adapt the definition of ProbpEx to incorporate anomalies in the final program. Then establish the following analog of Corollary 9.29: For all , , and , .

		9-6 (Pitt and Smith [151]) Establish the following analog of Proposition 9.33: For all and all m, with , .

		9-7 Prove: For all j, with and , . Observe that this result implies that, for all j, with , .

		9-8 Complete the proof of Proposition 9.36.

		9-9 Prove: For all j > 0 and , . Observe that this result implies that, for all j > 0, .

		9-10 Prove: For all i,, . Observe that this result implies that, for j, .