Probabilistic, nondeterministic, and alternating decision trees (Preliminary Version)
Udi Manber, Martin Tompa · 1982
This work generalizes decision trees in order to model algorithms which allow probabilistic, nondeterministic, or alternating control. Two geometric techniques for proving lower bounds on the time required by ordinary decision trees (Dobkin and Lipton's “region-counting” technique as applied to the knapsack and element uniqueness problems [1], and Reingold's technique as applied to set equality [4]) are shown to be special cases of one unified technique, which in fact applies to nondeterministic decision trees as well. This technique is applied to yield tight upper and lower bounds on the nondeterministic time for solving element uniqueness, set disjointness, set membership, set equality, ε-closeness [2], and knapsack problems, as well as many of these problems complements.