Complexity lower bounds for randomized computation trees over zero characteristic fields
Complexity lower bounds for randomized computation trees over zero characteristic fields
复制标题
零特征域上随机计算树的复杂度下界
DOI：
--
复制
发表时间：
1999
影响因子：
1.4
通讯作者：
D. Grigoriev
中科院分区：
文献类型：
--
作者：
D. Grigoriev
抽象的。我们得到了具有分支符号的随机计算树的非线性复杂度下界
$ \{=，\not=\} $在零字符域上。作为结果，我们得到
$ \Omega（n\，{\rm log}\，n）$不同性问题的下界，
$ \Omega（n^2）$背包问题的下界。对于更常见的随机计算树在实数与分支符号
在Grigoriev & Karpinski（1997）中的背包问题和Grigoriev（1999）中的独特性问题中证明了类似的界。
Abstract. We obtain nonlinear complexity lower bounds for randomized computation trees with branching signs
$ \{=,\not=\} $ over zero charac-teristic fields. As consequences we get the
$ \Omega(n\,{\rm log}\,n) $ lower bound for the distinctness problem and
$ \Omega (n^2) $ lower bound for the knapsack problem. For more customary randomized computation trees over the reals with branching signs
$ \{\le, >\} $, similar bounds were proved: for the knapsack problem in Grigoriev & Karpinski (1997) and for the distinctness problem in Grigoriev (1999).