The Boolean formula value problem is in ALOGTIME
The Boolean formula value problem is in ALOGTIME
复制标题
布尔公式值问题在ALOGTIME中
DOI：
10.1145/28395.28409
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
S. Buss
中科院分区：
文献类型：
--
作者：
S. Buss
布尔公式值问题在交替对数时间内，更一般地，括号上下文无关语言在交替对数时间内。逆波兰记数法布尔公式的求值也在交替的对数时间内。这些结果是最优的，因为布尔公式值问题对于确定性对数时间减少下的交替对数时间是完备的。因此，在AC0减少的情况下，交变对数时间也是完全的。
The Boolean formula value problem is in alternating log time and, more generally, parenthesis context-free languages are in alternating log time. The evaluation of reverse Polish notation Boolean formulas is also in alternating log time. These results are optimal since the Boolean formula value problem is complete for alternating log time under deterministic log time reductions. Consequently, it is also complete for alternating log time under AC 0 reductions.