On the Decisional Complexity of Problems Over the Reals

AbstractWe consider the role of randomness for the decisional complexity in algebraic decision (or computation) trees, i.e., the number of comparisons ignoring all other computation. Recently Ting and Yao showed that the problem of finding the maximum of n elements has decisional complexity O(log2n) (1994, Inform. Process. Lett., 49, 39–43). In contrast, Rabin showed in 1972 an Ω(n) bound for the deterministic case (1972, J. Comput. System Sci., 6, 639–650). We point out that their technique is applicable to several problems for which corresponding Ω(n) lower bounds hold. We show that in general the randomized decisional complexity is logarithmic in the size of the decision tree. We then turn to the question of the number of random bits needed to obtain the Ting and Yao result. We provide a deterministic O(k log n) algorithm for finding the elements which are larger than a given element, given a bound k on the number of these elements. We use this algorithm to obtain an O(log2n) random bits and O(log2n) queries algorithm for finding the maximum