Optimal bounds for decision problems on the CRCW PRAM

ABSTRACT

Optimal &OHgr;(log n/log log n) lower bounds on the time for CRCW PRAMS with polynomially bounded numbers of processors or memory cells to compute parity and a number of related problems are proven. A strict time hierarchy of explicit Boolean functions of n bits on such machines that holds up to &Ogr;(log n/log log n) time is also exhibited. That is, for every time bound T within this range a function is exhibited that can be easily computed using polynomial resources in time T but requires more than polynomial resources to be computed in time T - 1. Finally, it is shown that almost all Boolean functions of n bits require log n - log log n + &OHgr;(1) time when the number of processors is at most polynomial in n. The bounds do not place restrictions on the uniformity of the algorithms nor on the instruction sets of the machines.

REFERENCES

• 1: AJTAI, M. ~ }-Formulae on finite structures. Ann. Pure Appl. Logic 24, 1983, 1-48.
• 2: BLAME, P.W. Lower Bounds for Very Powerful Parallel Machines. Manuscript, 1985.
• 3: Paul Beame, Limits on the power of concurrent-write parallel machines, Information and Computation, v.76 n.1, p.13-28, January 1988 [doi>10.1016/0890-5401(88)90040-5]
• 4: Paul William Beame , S. A. Cook, Lower bounds in parallel machine computation, 1987
• 5: P. Beame , J. Hastad, Optimal bounds for decision problems on the CRCW PRAM, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.83-93, January 1987, New York, New York, United States [doi>10.1145/28395.28405]
• 6: BOLLOB,~S, B. Random Graphs. Academic Press, Orlando, Fla., 1985.
• 7: CHANDRA, A. K., STOCKMEYER, L. J., AND VISHKIN, U. Constant depth reducibility, SIAM J. Comput. 13, 2 (1984), 423-439.
• 8: ERDOS, P., AND SPENCER, J. Probabilistic Methods in Combinatorics. Academic Press, Orlando, Fla., 1974.
• 9: FURST, M., SAXE, J. B., AND SIPSER, M. Parity, circuits, and the polynomial time hierarchy, Math. Syst. Theory 17, 1 (1984), 13-28.
• 10: J Hastad, Almost optimal lower bounds for small depth circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.6-20, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12132]
• 11: Johan Håstad, Computational limitations of small-depth circuits, MIT Press, Cambridge, MA, 1987
• 12: KUCERA, L. Parallel computation and conflicts in memory access. Inf. Proc. Lett. 14, 2 (1982), 93-96.
• 13: Ming Li , Yaacov Yesha, New lower bounds for parallel computation, Journal of the ACM (JACM), v.36 n.3, p.671-680, July 1989 [doi>10.1145/65950.65959]
• 14: Michael Sipser, Borel sets and circuit complexity, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.61-69, December 1983 [doi>10.1145/800061.808733]
• 15: STOCKMEYER, L. J., AND VISHK,N, U. Simulation of parallel random access machines by circuits. SIAM J. Comput. 13, 2 (1984), 404-422.
• 16: Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Theory