EXACT LOWER TIME-BOUNDS FOR COMPUTING BOOLEAN FUNCTIONS ON CREW PRAMS

The time complexity of Boolean functions on abstract concurrent-read e xclusive-write parallel random access machines (CREW PRAMs) is conside red. We improve results of Cook, Dwork, and Reischuk (SIAM J. Comput. 15 (1986), 87-97), and extend work of Kutylowski (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 b ounds, which works for many Boolean functions, in particular all symme tric functions. The new approach is based on the fact that Boolean fun ctions can be represented as polynomials with integer coefficients and that the degree of such a polynomial can be taken as a complexity mea sure. For some functions, eg., AND and PARITY, the exact time bound al so 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 func tions in the bounded error model. We further show that the (bounded er ror) probabilistic time complexity of Boolean functions on CREW PRAMs differs at most by a constant factor from the deterministic time compl exity. We also obtain exact bounds for machines that allow a few proce ssors to try to write to the same cell simultaneously. These bounds ar e stronger than those which follow automatically from the exclusive-wr ite bounds. No tight bounds for this model were known before. (C) 1994 Academic Press, inc,