The complexity of problems on probabilistic, nondeterministic, and alternating decision trees

Publisher Website
Google Scholar
Abstract
This work generalizes decision trees in order to study lower bounds on the running times of algorithms that allow probabilistic, nondeterministic, or alternating control. It is shown that decision trees that are allowed internal randomization (at the expense of introducing a small probability of error) run no faster asymptotically than ordinary decision trees for a collection of natural problems. Two geometric techniques from the literature for proving lower bounds on the time required by ordinary decision trees are shown to be special cases of one unified technique that, in fact, applies to nondeterministic decision trees as well. Finally, it is shown that any lower bound on alternating decision tree time also applies to alternating Turing machine time.

This publication has 5 references indexed in Scilit: