期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove an exponential lower bound on the size of any
fixed-degree algebraic decision tree for solving MAX, the
problem of finding the maximum of n real numbers. This
complements the n−1 lower bound of Rabin \cite{R72} on
the depth of algebraic decision trees for this problem.
The proof in fact gives an exponential lower bound on size
for the polyhedral decision problem MAX= of testing whether
the j-th number is the maximum among a list of n real
numbers. Previously, except for linear decision trees, no
nontrivial lower bounds on the size of algebraic decision
trees for any familiar problems are known. We also establish
an interesting connection between our lower bound and the
maximum number of minimal cutsets for any rank-d hypergraphs
on n vertices.
