4
$\begingroup$

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?

$\endgroup$
  • 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 Nikolov Jul 15 '16 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 Grochow Jul 19 '16 at 3:31
  • $\begingroup$ @JoshuaGrochow thanks! I was pretty I was missing something. $\endgroup$ – Sasho Nikolov Jul 19 '16 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$ – Sadguru Jul 25 '16 at 6:38
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

This was also done, independently, by Lubiw and Racz in 1991. See http://www.sciencedirect.com/science/article/pii/089054019190034Y .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.