Some complexity questions related to distributive computing(Preliminary Report) 论文

摘要

Let M = {0, 1, 2, ..., m—1} , N = {0, 1, 2,..., n—1} , and f:M × N → {0, 1} a Boolean-valued function. We will be interested in the following problem and its related questions. Let i ε M, j ε N be integers known only to two persons P1 and P2, respectively. For P1 and P2 to determine cooperatively the value f(i, j), they send information to each other alternately, one bit at a time, according to some algorithm. The quantity of interest, which measures the information exchange necessary for computing f, is the minimum number of bits exchanged in any algorithm. For example, if f(i, j) = (i + j) mod 2. then 1 bit of information (conveying whether i is odd) sent from P1 to P2 will enable P2 to determine f(i, j), and this is clearly the best possible.