On the P versus NP intersected with co-NP question in communication complexity

Stasys Jukna

Abstract.

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 its deterministic and/or probabilistic communication complexity? 

In the \emph{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 \emph{best} partition model of communication  the situation is entirely different: here P is a \emph{proper} subset even of RP\cap co-RP.  This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982.