The element distinctness problem asks whether any two elements of the input sequence $<x_1,\ldots,x_n>$ are equal? This problem has a lower bound of $\Omega(n \log n)$ in the algebraic decision tree model when the $x_i$'s are real numbers. My question is what is the lower bound if we restrict the $x_i$'s to positive integers?
4
-
5$\begingroup$ I may be missing something, but I don't think it makes a difference since there is a positive integer input in any of the $n!$ connected components of NO instances, and the algebraic decision tree must still separate them. $\endgroup$– Sasho NikolovJul 15, 2016 at 14:46
-
2$\begingroup$ @SashoNikolov: It is conceivable that having to only solve the problem on integer instances might be easier than solving it on all real instances. Also, the proof for the reals uses the notion of "connected component" in a pretty crucial way, so it's certainly not obvious that the proof carries over. Nonetheless, such a lower bound for the integers is known (see my answer). $\endgroup$– Joshua GrochowJul 19, 2016 at 3:31
-
$\begingroup$ @JoshuaGrochow thanks! I was pretty I was missing something. $\endgroup$– Sasho NikolovJul 19, 2016 at 14:30
-
$\begingroup$ Thanks a lot. The comments helped me understand the nuances one needs to be aware of when the domain changes from reals to integers. $\endgroup$– SadguruJul 25, 2016 at 6:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
Such a lower bound for integer inputs is indeed known, and is not just a trivial consequence of the result for the reals:
A. C.-C. Yao, Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains, SIAM J. Comput., 20(4), 655–668.
Rather, Yao has to re-prove the Milnor-Thom-Oleinik-Petrovski bound on the number of connected components of a semi-algebraic variety over $\mathbb{R}$ more or less from scratch to get it to work over $\mathbb{Q}$, where the notion of connectedness is a bit thornier. He also needs to assume that the problem is scale-invariant and "rationally dispersed" (see the paper), and only counts connected components of nonzero measure. These technical conditions already hint that it is not a simple consequence of the result over the reals.
answered Jul 19, 2016 at 3:30
$\begingroup$
$\endgroup$
0
This was also done, independently, by Lubiw and Racz in 1991. See http://www.sciencedirect.com/science/article/pii/089054019190034Y .
