Difference between revisions of "Complexity Zoo:List of Communication Complexity Classes"

From Complexity Zoo
Jump to navigation Jump to search
m
m
 
(7 intermediate revisions by the same user not shown)
Line 5: Line 5:
  
 
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., P<sup>cc</sup>(f) may refer to the deterministic communication complexity of f, while [[Complexity Zoo:P#pcc|P<sup>cc</sup>]] also stands for the class of all f for which P<sup>cc</sup>(f) is at most polylog(n).)
 
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., P<sup>cc</sup>(f) may refer to the deterministic communication complexity of f, while [[Complexity Zoo:P#pcc|P<sup>cc</sup>]] also stands for the class of all f for which P<sup>cc</sup>(f) is at most polylog(n).)
 +
 +
Often, inclusions between communication complexity classes, such as [[Complexity Zoo:M#macc|MA<sup>cc</sup>]]&sube;[[Complexity Zoo:A#amcc|AM<sup>cc</sup>]], hold for exactly the same reasons as they do for the corresponding classical complexity classes.
  
 
For surveys on two-party communication complexity classes (as well as sources of many of the original definitions), see [[zooref#bfs86|[BFS86]]], [[zooref#hr90|[HR90]]], [[zooref#gpw16b|[GPW16b]]].
 
For surveys on two-party communication complexity classes (as well as sources of many of the original definitions), see [[zooref#bfs86|[BFS86]]], [[zooref#hr90|[HR90]]], [[zooref#gpw16b|[GPW16b]]].
Line 10: Line 12:
 
Two-party classes:
 
Two-party classes:
  
[[#paritypcc|&#8853;P<sup>cc</sup>]] -  
+
[[Complexity Zoo:Symbols#paritypcc|&#8853;P<sup>cc</sup>]] -
 +
[[Complexity Zoo:A#amcc|AM<sup>cc</sup>]] -  
 
[[Complexity Zoo:B#bppcc|BPP<sup>cc</sup>]] -  
 
[[Complexity Zoo:B#bppcc|BPP<sup>cc</sup>]] -  
 
[[Complexity Zoo:C#conpcc|coNP<sup>cc</sup>]] -  
 
[[Complexity Zoo:C#conpcc|coNP<sup>cc</sup>]] -  
 +
[[Complexity Zoo:M#macc|MA<sup>cc</sup>]] -
 
[[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] -
 
[[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] -
 
[[Complexity Zoo:P#pcc|P<sup>cc</sup>]] -  
 
[[Complexity Zoo:P#pcc|P<sup>cc</sup>]] -  
 
[[Complexity Zoo:P#phcc|PH<sup>cc</sup>]] -  
 
[[Complexity Zoo:P#phcc|PH<sup>cc</sup>]] -  
 +
[[Complexity Zoo:P#pnpcc|P<sup>NPcc</sup>]] -
 +
[[Complexity Zoo:P#postbppcc|PostBPP<sup>cc</sup>]] -
 
[[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]] -  
 
[[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]] -  
 
[[Complexity Zoo:P#pspacecc|PSPACE<sup>cc</sup>]] -  
 
[[Complexity Zoo:P#pspacecc|PSPACE<sup>cc</sup>]] -  
 
[[Complexity Zoo:R#rpcc|RP<sup>cc</sup>]] -
 
[[Complexity Zoo:R#rpcc|RP<sup>cc</sup>]] -
 
[[Complexity Zoo:S#sbpcc|SBP<sup>cc</sup>]] -
 
[[Complexity Zoo:S#sbpcc|SBP<sup>cc</sup>]] -
 +
[[Complexity Zoo:U#uamcc|UAM<sup>cc</sup>]] -
 
[[Complexity Zoo:U#upcc|UP<sup>cc</sup>]] -
 
[[Complexity Zoo:U#upcc|UP<sup>cc</sup>]] -
 +
[[Complexity Zoo:U#upostbppcc|UPostBPP<sup>cc</sup>]] -
 
[[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]] -
 
[[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]] -
[[Complexity Zoo:U#usbpcc|USBP<sup>cc</sup>]]
+
[[Complexity Zoo:U#usbpcc|USBP<sup>cc</sup>]] -
 +
[[Complexity Zoo:U#uwappcc|UWAPP<sup>cc</sup>]] -
 +
[[Complexity Zoo:W#wappcc|WAPP<sup>cc</sup>]] -
 +
[[Complexity Zoo:Z#zamcc|ZAM<sup>cc</sup>]] -
 +
[[Complexity Zoo:Z#zppcc|ZPP<sup>cc</sup>]]
  
 
Multi-party number-on-forehead classes:
 
Multi-party number-on-forehead classes:

Latest revision as of 00:04, 10 June 2016

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.

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).)

Often, inclusions between communication complexity classes, such as MAccAMcc, hold for exactly the same reasons as they do for the corresponding classical complexity classes.

For surveys on two-party communication complexity classes (as well as sources of many of the original definitions), see [BFS86], [HR90], [GPW16b].

Two-party classes:

⊕Pcc - AMcc - BPPcc - coNPcc - MAcc - NPcc - Pcc - PHcc - PNPcc - PostBPPcc - PPcc - PSPACEcc - RPcc - SBPcc - UAMcc - UPcc - UPostBPPcc - UPPcc - USBPcc - UWAPPcc - WAPPcc - ZAMcc - ZPPcc

Multi-party number-on-forehead classes:

BPPcc - NPcc - RPcc - Pcc -