Algorithms for Boolean Formula Evaluation and for Tree Contraction
Samuel R. Buss · 1991
This paper presents a new, simpler ALOGTIME 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 ∧ and ∨ 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.