An Optimal Parallel Algorithm for Formula Evaluation
An Optimal Parallel Algorithm for Formula Evaluation
复制标题
公式评估的最优并行算法
DOI：
10.1137/0221046
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
V. Ramachandran
中科院分区：
文献类型：
--
作者：
S. Buss;S. Cook;A. Gupta;V. Ramachandran
Buss ${\textbf{NC}}^1 $算法的新方法[Proc. 19 th ACM Symposium on Theory of Computing，Association for Computing Machinery，纽约，1987，pp. 123-131]的布尔公式的评价。这个问题被证明是完全的${\textbf{AC}}^0 $$减少${\textbf{NC}}^1 $。然后，这种方法被用来解决更一般的问题，评估算术公式使用算术电路。
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.