On span-Pcc and related classes in structural communication complexity
Wunderlich, Henning · OPen Access Repositorium der Universität Ulm (OPARU) (Ulm University) · 2008
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 ot\subseteq #P, max-P \subsetneq span-P 3. min-P eq max-P, min-P ot\subseteq span-P.