The Boolean formula value problem is in ALOGTIME 论文

1987引用 241
DOI
Complexity and Algorithms in GraphsCryptography and Data SecurityQuantum Computing Algorithms and Architecture
网络安全Quantum Computing Algorithms and ArchitectureCryptography and Data SecurityComplexity and Algorithms in Graphs
相关技术:Complexity and Algorithms in GraphsQuantum Computing Algorithms and Architecture
关系图谱

1

作者

2

相关技术

0

相关事件

0

相关文章

摘要

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 reductions.

作者查看全部 (1)

S

Sam Buss

相关技术查看全部 (2)

Complexity and Algorithms in GraphsQuantum Computing Algorithms and Architecture

相关事件

暂无数据

相关文章

暂无数据