Research article:

Samuel R. Buss.
"Algorithms for Boolean formula evaluation and for tree-contraction."

In Proof Theory, Complexity, and Arithmetic, P. Clote and J. Krajicek (eds), Oxford University Press, 1993, pp. 95-115.

Download article: postscript or PDF

Abstract: This paper presents a new, simpler ALOGTIME (alternating logtime) algorithm for the Boolean sentence value problem (BSVP). Unlike prior work, this algorithm avoids the use of postfix-longer-operand-first formulas. This paper also shows that tree-contraction can be made ALOGTIME uniform.
The Boolean sentence problem restricted to balanced sentences with only the connectives \$\land\$ and \$\lor\$ is in online \$O(\log(\log n))\$ space. Hence every ALOGTIME predicate is deterministic log-time reducible to \$\log(\log n)\$ space. This balanced and/or BSVP has logarithmic width, linear length, branching programs.

Back to Sam Buss's publications page.