An optimal parallel algorithm for formula evaluation. (English) Zbl 0825.68424

Buss, S.; Cook, S.; Gupta, Arvind; Ramachandran, V.

SIAM J. Comput. 21, No. 4, 755-780 (1992).

Summary: A new approach to the first author’s \(NC^1\) algorithm [in: Proceedings of the Nineteenth ACM Symposium on Theory of Computing (New York, 1987), 123–131, ACM, New York (1987)] for evaluation of Boolean formulas is presented. This problem is shown to be complete for \(NC^1\) over \(AC^0\) reductions. This approach is then used to solve the more general problem of evaluating arithmetic formulas by using arithmetic circuits.

MSC:

68Q25	Analysis of algorithms and problem complexity
68W15	Distributed algorithms