An Optimal Parallel Algorithm for Formula Evaluation
Authors:
- S. Cook S. BussSBS. Cook S. Buss
- S. CookSCS. Cook
- A. GuptaAGA. Gupta
- V. RamachandranVRV. Ramachandran
- Martin BeaudryMBMartin Beaudry
- Pierre McKenziePMPierre McKenzie
- Pierre PéladeauPPPierre Péladeau
- Denis ThérienDTDenis Thérien
- Nader H. BshoutyNBNader H. Bshouty
- Richard CleveRCRichard Cleve
- Wayne EberlyWEWayne Eberly
- Eric AllenderEAEric Allender
- 1 August 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (4) , 755-780
Abstract
A new approach to Buss’s ${\textbf{NC}}^1 $ algorithm [Proc. 19th ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1987, pp. 123–131] for evaluation of Boolean formulas is presented. This problem is shown to be complete for ${\textbf{NC}}^1 $ over ${\textbf{AC}}^0 $ reductions. This approach is then used to solve the more general problem of evaluating arithmetic formulas by using arithmetic circuits.
Keywords
This publication has 19 references indexed in Scilit:
- On uniformity within NC1Journal of Computer and System Sciences, 1990
- Expressibility and Parallel ComplexitySIAM Journal on Computing, 1989
- Input-driven languages are in log n depthInformation Processing Letters, 1988
- Speedups of deterministic machines by synchronous parallel machinesJournal of Computer and System Sciences, 1985
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- A complexity theory for unbounded fan-in parallelism1982
- Some Exact Complexity Results for Straight-Line Computations over SemiringsJournal of the ACM, 1982
- AlternationJournal of the ACM, 1981
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974