Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

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 -&-ldquo;region-counting-&-rdquo; 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, -&-egr;-closeness [2], and knapsack problems, as well as many of these problems complements. In section 3 we present evidence that probabilistic decision trees have lower bounds matching the deterministic upper bounds for many of the problems mentioned above, and that they are not substantially more powerful for any similar problems. In section 4 it is shown that non-logarithmic lower bounds on the time required by alternating decision trees will not be easy to demonstrate, because such lower bounds would also apply to time on the seemingly more general alternating Turing machine model.

REFERENCES

• 1: Dobkin, D.P. and Lipton, R.J., On the Complexity of Computations Under Varying Sets of Primitives, Journal of Computer and System Sciences 18 (1979), 86-91.
• 2: Michael L. Fredman , Bruce Weide, On the complexity of computing the measure of ∪[a_i,b_i], Communications of the ACM, v.21 n.7, p.540-544, July 1978 [doi>10.1145/359545.359553]
• 3: Manber, U. and Tompa, M., The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem, 22nd Annual Symposium on Foundations of Computer Science (October 1981), 220-227.
• 4: Edward M. Reingold, On the Optimality of Some Set Algorithms, Journal of the ACM (JACM), v.19 n.4, p.649-659, Oct. 1972 [doi>10.1145/321724.321730]
• 5: Ruzzo, W.L., On Uniform Circuit Complexity, Journal of Computer and System Sciences 22, 3 (June 1981), 365-383.
• 6: Tompa, M., Time-Space Tradeoffs for Straight-Line and Branching Programs, Ph.D. Thesis, University of Toronto, July 1978. Available as Department of Computer Science Technical Report No. 122/78.
• 7: Wallace, C., A Suggestion for a Fast Multiplier, IEEE Trans. Elec. Comp. EC-13 (February 1964), 14-17.