Complexity lower bounds for randomized computation trees over zero characteristic fields
We obtain nonlinear complexity lower bounds for randomized computation trees with branching signs {=, not equal} over zero characteristic fields. As consequences we get the Ohm(nlogn) lower bound for the distinctness problem and Ohm(n(2)) lower bound for the knapsack problem. For more customary randomized computation trees over the reals with branching signs {less than or equal to,>}, similar bounds were proved: for the knapsack problem in Grigoriev & Karpinski (1997) and for the distinctness problem in Grigoriev (1999).
randomized computation trees distinctness problem knapsack problem multiplicative complexity