非表示:
キーワード:
-
要旨:
In this paper, we prove two general lower bounds for algebraic
decision trees which test membership in a set $S\subseteq\Re^n$ which is
defined by linear inequalities.
Let $rank(S)$ be
the maximal dimension of a linear subspace contained in the closure of
$S$.
% \endgraf
First we prove that any decision tree which uses multilinear
functions (i.e.~arbitrary
products of linear functions) must have depth
at least $n-rank(S)$.
This solves an open question raised by A.C.~Yao
and can be used to show
that multilinear functions are not really more powerful
than simple comparisons between the input variables when
computing the largest $k$ elements of $n$ given numbers.
Yao could only prove this result in the special case when
products of at most two linear functions are used.
Our proof is based on a dimension argument.
It seems to be the first time that such an approach
yields good lower bounds for nonlinear decision trees.
% \endgraf
Surprisingly, we can use the same methods to give an
alternative proof for Rabin's fundamental Theorem,
namely that the depth of any decision tree using arbitrary
analytic functions is at least $n-rank(S)$.
Since we show that Rabin's original proof is incorrect,
our proof of Rabin's Theorem is not only the first correct one
but also generalizes the Theorem to a wider class of functions.
