Optimal bounds for decision problems on the CRCW PRAM

ABSTRACT

We prove optimal &OHgr;(log n/log log n) lower bounds on the time for CRCW PRAM's with polynomially bounded numbers of processors or memory cells to compute parity and a number of related problems. We also exhibit a strict time hierarchy of explicit Boolean functions of n bits on such machines which holds up to &Ogr;(log n/log log n) time. Furthermore, we show 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. Our bounds do not place restrictions on the uniformity of the algorithms nor on the instruction sets of the machines.

REFERENCES

• Aj: Ajtai, M. E}-Formulae on Finite Structures, Annals of Pure and Applied Logic, vol. 24, 1983, pp. 1-48.
• Be1: Beame, P.W. Lower Bounds for very Pow. er{ul Parallel Machines, manuscript, 1985.
• Be2: P Beame, Limits on the power of concurrent-write parallel machines, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.169-176, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12147]
• Be3: Paul William Beame , S. A. Cook, Lower bounds in parallel machine computation, 1987
• CSV: Chandra, A.K., Stockmeyer, L.J., and Vishkin, U. Constant Depth Reducibility, SIAM J. Computing, vol 13(2), 1984, pp. 423-439.
• Ch: Chor, B. private communication, 1986.
• FSS: Furst, M., Saxe, J.B., and Sipser, M. Parity, Circuits, and the Polynomial Time tlierarchy, Mathematical Systems Theory, vol. 17, no. 1, 1984, pp. 13-28.
• Ha1: 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]
• Ha2: Hastad, J. Computational Limitations for Small Depth Circuits, Ph.D. Thesis, M.I.T., 1986.
• Ku: Kucera, L. Parallel Computation and Conflicts in Memory Access, Information Processing Letters, vol. 14, no. 2, 1982, pp. 9:3-96.
• LY: M Li , Y Yesha, New lower bounds for parallel computation, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.177-187, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12148]
• Ru: Ruzzo, W.L. private colnmunication, 1986.
• Si: 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]
• SV: Stocklneyer, L.J., and Vishkin, U. Simulation of Parallel Random Access Machines by Circuits, SiAM J. Computing, vol 13(2), 1984, pp. 404-422.
• Ya: 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

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Decision problems

General Terms:
Languages, Theory, Verification