Some complexity questions related to distributive computing(Preliminary Report)

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