We consider the analog of the P versus NP $\cap$ co-NP question for the classical two-party communication protocols where polynomial time is replaced by poly-logarithmic communication: if both a boolean function $f$ and its negation $\neg f$ have small (poly-logarithmic in the number of variables) nondeterministic communication complexity, what is then the deterministic and/or probabilistic communication complexity of $f$?
In the fixed (worst) partition model of communication this question was answered by Aho, Ullman and Yannakakis in 1983: here P = NP $\cap$ co-NP.
We show that in the best partition model of communication the situation is entirely different: here P is a proper subset even of RP $\cap$ co-RP. This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982.