Complexity Zoo:List of Communication Complexity Classes

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

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.

BPP^cc - BPP_$k$^cc - coNP^cc - P^cc - P_$k$^cc - PH^cc - PP^cc - RP_$k$^cc - NP^cc - NP_$k$^cc - UPP^cc