PROBABILISTIC BOOLEAN DECISION TREES AND THE COMPLEXITY OF EVALUATING GAME TREES.

The power of randomness in the Boolean decision-tree model is studied, and separation results among three complexity measures are proved. The results are obtained using general and efficient methods for computing upper and lower bounds on the probabilistic complexity of evaluating Boolean formulas in which every variable appears exactly once (AND/OR tree with distinct leaves). These bounds are shown to be exactly tight for interesting families of such tree functions. The results are then applied to the complexity of evaluating game trees. These trees are similar to Boolean tree functions, except that input variables (leaves) may take values from a large set (of valuations to game positions) and the AND/OR nodes are replaced by MIN/MAX nodes. The best known algorithm for this problem is the alpha-beta pruning method. A randomized variant of alpha-beta pruning is analyzed, and it is shown that it is considerably faster than the deterministic variant in the case and optimal for uniform trees.