|
University of Bonn -> Department of Computer Science -> Chair V | ||
CS-Reports 1995 | Copyright 1995 University of Bonn, Department of Computer Science, Abt. V | |
85143
|
A Lower Bound on the Size of Algebraic Decision Trees for the MAX Problem
Dima Grigoriev, Marek Karpinski, Andrew Yao [Download PostScript] [Download PDF] We prove an exponential lower bound on the size of (ternary) algebraic decision trees for the MAX Problem of finding maximum of n real numbers. This complements $n-1$ lower bound (cf\@. M. O. Rabin \cite{R72}) on the depth of algebraic decision trees for this problem. The method yields also for the first time a lower size bound for a polyhedral decision problem MAX= of testing whether the $ith$ number is the maximum among a list of n real numbers, and gives the first nonlinear size lower bound on algebraic decision trees for the selection problems. |
|
Last Change:
08/18/99 at 13:00:38
Deutsch |
University of Bonn -> Department of Computer Science -> Chair V |