In this revised version one new result is added: we show that
NP is not a subset of BPP in the best-partition case. This
extends the same result of Rabin and Yao from the fixed-partition
case to the best-partition model.

We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and Yannakakis in 1983: here P=NP\cap coNP.
<p>
We show that in the best-partition case the situation is entirely different: here P is a proper subset of NP\cap coNP. This resolves an open question raised by Papadimitriou and Sipser in 1982. Actually, we prove even stronger separations in this case:
P is a proper subset of RP\cap coRP, and NP\cap coN is no longer a subset of BPP.

In the Revision 1 of ECCC Report Nr. 62 the following two changes should be
made (I am thankful to Hartmut Klauck for pointing to this):

1. In the last sentence of the abstract it should be "BPP is not a subset of NP".

2. In Theorem 2.1 and Lemma 3.1 replace "are constants" by "are O(\log n)".