Exact lower time bounds for computing Boolean functions on CREW PRAMs

摘要

The time complexity of Boolean functions on abstract concurrent-read exclusive-write parallel random access machines (CREW PRAMs) is considered. We improve results of Cook, Dwork, and Reischuk (SIAM J. Comput. 15 (1986), 87–97), and extend work of Kutyłowski (SIAM J. Comput. 20 (1991), 824–833), who proved a lower time bound for the OR function on such machines that equals the upper bound. We provide a general means for obtaining exact (i.e., correct up to an additive constant) lower bounds, which works for many Boolean functions, in particular all symmetric functions. The new approach is based on the fact that Boolean functions can be represented as polynomials with integer coefficients and that the degree of such a polynomial can be taken as a complexity measure. For some functions, e.g., AND and PARITY, the exact time bound also holds for nondeterministic machines. For probabilistic machines, we obtain exact lower time bounds for PARITY in the unbounded error model and, utilizing results by Szegedy (Ph.D. dissertation, University of Chicago, 1989), prove a general lower bound valid for all Boolean functions in the bounded error model. We further show that the (bounded error) probabilistic time complexity of Boolean functions on CREW PRAMs differs at most by a constant factor from the deterministic time complexity. We also obtain exact bounds for machines that allow a few processors to try to write to the same cell simultaneously. These bounds are stronger than those which follow automatically from the exclusive-write bounds. No tight bounds for this model were known before.