Communication complexity

1 January 1982

conference paper
Published by Association for Computing Machinery (ACM)

p. 196-200
https://doi.org/10.1145/800070.802192

Abstract

In this paper we prove several results concerning this complexity measure. First we establish (in a non-constructive manner) that there exist languages which cannot be recognized with less than n communication (obviously, communication n is always enough for recognizing any language). In fact, we show that for any functionf(n)-&-lt; n, there are languages recognizable with communicationf(n) but not with communicationf (n)-&-minus;1. In other words, this complexity measure possesses a very dense hierarchy or complexity classes, as miniscule increments in communication add to the languages that can be recognized.

Keywords

COMMUNICATION N
NON-CONSTRUCTIVE MANNER
MINISCULE INCREMENT
COMPLEXITY MEASURE
DENSE HIERARCHY
COMPLEXITY CLASS
COMMUNICATION COMPLEXITY
N COMMUNICATION

This publication has 0 references indexed in Scilit: