On span-Pcc and related classes in structural communication complexity

Abstract

The complexity classes #P, #NP, min-P, max-P, opt-P and span-P are well known in structural complexity. We define analogous classes in (structural) communication complexity and study some of their properties, e.g. establishing the inclusions #P \subseteq span-P, span-P \subseteq #NP and max-P \subseteq span-P. Especially, in contrast to the current state of affairs in time complexity, we are able to prove the following separations: 1. #P \subsetneq span-P \subsetneq #NP 2. max-P \not\subseteq #P, max-P \subsetneq span-P 3. min-P \neq max-P, min-P \not\subseteq span-P.