An Optimal Parallel Algorithm for Formula Evaluation

Authors:
  • SBS. Cook S. Buss
    S. Cook S. Buss
  • SCS. Cook
    S. Cook
  • AGA. Gupta
    A. Gupta
  • VRV. Ramachandran
    V. Ramachandran
  • MBMartin Beaudry
    Martin Beaudry
  • PMPierre McKenzie
    Pierre McKenzie
  • PPPierre Péladeau
    Pierre Péladeau
  • DTDenis Thérien
    Denis Thérien
  • NBNader H. Bshouty
    Nader H. Bshouty
  • RCRichard Cleve
    Richard Cleve
  • WEWayne Eberly
    Wayne Eberly
  • EAEric Allender
    Eric Allender

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.

This publication has 19 references indexed in Scilit: