SIZE-DEPTH TRADEOFFS FOR BOOLEAN-FORMULAS

被引：23

作者：

BONET, ML ^{[1
]}

BUSS, SR ^{[1
]}

机构：

[1] UNIV CALIF SAN DIEGO,DEPT MATH,LA JOLLA,CA 92093

来源：

INFORMATION PROCESSING LETTERS | 1994年 / 49卷 / 03期

基金：

美国国家科学基金会;

关键词：

THEORY OF COMPUTATION; BOOLEAN FORMULAS; FORMULA COMPLEXITY; SIZE-DEPTH TRADEOFF;

D O I：

10.1016/0020-0190(94)90093-0

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a simplified proof that Brent/Spira restructuring of Boolean formulas can be improved to allow a Boolean formula of size n to be transformed into an equivalent log depth formula of size O(n(alpha)) for arbitrary alpha > 1.

引用

页码：151 / 155

页数：5