Complexity Zoo:List of Communication Complexity Classes
Communication complexity deals with how much data must be exchanged between parties cooperating to compute a function whose input is split amongst them. Many computational complexity classes have communication complexity analogues. For convenience, we list here those analogues present in the Zoo.
In the literature, these names sometimes refer to classes of total functions, and sometimes refer to classes of partial functions (promise problems); for some classes this makes a big difference! Also, in the literature, these class names are sometimes overloaded to refer to the corresponding communication complexity measure (e.g., Pcc(f) may refer to the deterministic communication complexity of f, while Pcc also stands for the class of all f for which Pcc(f) is at most polylog(n).)
Multi-party number-on-forehead classes: