Resource bounds for parallel computation of threshold and symmetric functions

摘要

We prove that a PRIORITY PRAM with one shared memory cell and number of processors linear in n requires Ω(g(n)) time in order to decide if a binary vector of length n has at least g(n) 1's, for the case g(n) = o(n14). This is the decision problem for the threshold languageLg Our lower bound is tight. For PRIORITY with m shared memory cells we prove an Ω(g(n)/m) lower bound. We also show that with an exponential number of processors Lg can be decided by the same model in O(√g(n)) time. Our results complement the results of Vishkin and Wigderson, who showed that Ω(√(g(n)) is a lower bound for Lg. Their lower bound does not depend on the number of processors. We obtain a stronger bound when the number of processors is linear in the number of inputs. Our technique for threshold languages enables us to show that for a large range of number of processors, PRIORITY and ARBITRARY with one shared memory cell require the same time complexity for computing large classes of symmetric functions. For models without ROM (i.e., each processor has access to only one input) an analogous result was proved by Li and Yesha. Next we consider probabilistic PRIORITY (i.e., with randomization). We show that a probabilistic PRIORITY with m ⩽ nϵ, (0 ⩽ ϵ < 1) shared memory cells and any finite number of processors requires expected time more than ((1 − ϵ)/4) log n to compute PARITY of n bits. (The limitation on the amount of shared memory is important, since with enough processors and shared memory PRIORITY can compute PARITY in constant time even deterministically.) For probabilistic PRIORITY without ROM we prove an Ω(n/m) lower bound which is tight when m = O(n/log n).