Unbounded fan-in circuits and associative functions

ABSTRACT

We consider the computation of finite semigroups using unbounded fan-in circuits. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup in fact does not contain a group, then for any primitive recursive function f, circuits of size O(nf−1(n)) and constant depth exist for the semigroup product of n elements. The depth depends upon the choice of the primitive recursive function f. The circuits not only compute the semigroup product, but every prefix of the semigroup product. A consequence is that the same bounds apply for circuits computing the sum of two n-bit numbers.

REFERENCES

• 1: Stephen Cook , Cynthia Dwork, Bounds on the time for parallel RAM's to compute simple functions, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.231-233, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802196]
• 2: A.K. Chandra, S. Fortune, R. Lipton, "Lower Bounds for Constant Depth Monotone Circuits for Prefix Functions," to appear.
• 3: A.K. Chandra, L.J. Stockmeyer, U. Vishkin, "A Complexity Theory for Unbounded Fan-in Parallelism," Proceedings 23rd Annual Symposium on the Foundations of Computer Science, 1982, pp. 1-13.
• 4: D. Dolev, C. Dwork, N. Pippenger, and A. Wigderson, "Superconcentrators, generalizers and generalized concentrators with limited depth," this Proceedings.
• 5: Faith Ellen Fich, Two problems in concrete complexity: cycle detection and parallel prefix computation, 1982
• 6: M. Furst, J. Saxe, M. Sipser, "Parity, Circuits, and the Polynomial-time Hierarchy," Proceedings of the 22nd Annual Symposium on the Foundations of Computer Science, 1981, pp. 260-270.
• 7: O. Gabber and Z. Galil, "Explicit Constructions of Linear Size Concentrators," Proceedings of the 20th Annual Symposium on the Foundations of Computer Science, 1979, pp. 364-370.
• 8: Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
• 9: Robert McNaughton , Seymour A. Papert, Counter-Free Automata (M.I.T. research monograph no. 65), The MIT Press, 1971
• 10: R. Reischuk, "A Lower Time Bound for Parallel Random Access Machines without Simultaneous Writes," Report RJ3431, IBM Research Lab, San Jose, Ca, 1982.
• 11: Y. Shiloach and U. Vishkin, "Finding the Maximum, Merging, and sorting in a Parallel Computation Model," J. of Algorithms 2 (1981), pp. 88-102.
• 12: C. Tung, "Arithmetic", in Computer Science, A.F. Cardenas, L. Presser, and M.A. Marin, Eds., Wiley-Intersceince, New York, 1972.
• 13: Leslie G. Valiant, On non-linear lower bounds in computational complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.45-53, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803752]
• 14: U. Vishkin "Implementation of Simultaneous Memory Access in Models that Forbit it," Tech Report No 210, Dept of Computer Science, Technion, Haifa, Israel, 1981.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

General Terms:
Theory