Page 212

		Thus, the team hierarchy is contained in the probabilistic hierarchy. However, it turns out that the probabilistic hierarchy is no finer than the team hierarchy. To see this, let . Clearly, . Now, by Theorem 9.24, . But, Corollary 9.27 implies that . Thus, . We have essentially shown the following corollary, which says that the probabilistic hierarchy is exactly the same as the team hierarchy.

		9.29 Corollary (Pitt [149, 150]) For each and each , .

		§9.5

		Corollary 9.29 can be used to characterize generalized team identification paradigms in which more than one member of the team is required to be successful. To make this clear we rely on the following definition.

		9.30 Definition For each , let , where is such that .

		It is easy to verify that for , . The next result is simply a restatement of Corollary 9.29 using this notion.

		9.31 Corollary (Pitt and Smith [151]) For each , we have .

		The following result says that all collections of functions that can be identified by a team of n scientists with the requirement that at least m out of n are successful can also be identified by a single probabilistic scientist with probability .

		9.32 Proposition (Pitt and Smith [151]) Suppose and . Then, .

		Proof: Let . Let M1, M2, . . . , Mn be (deterministic) scientists witnessing . Let P be a probabilistic scientist equipped with an n-sided coin. The behavior of P can be described thus: P, before receiving any input, flips its n-sided coin and obtains a number , P then simulates the deterministic scientist Mi+l. Clearly, for each , . Hence, .