13
$\begingroup$

There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's simple enough to use in a first course in algorithm analysis and design. The same “level of difficulty” as the lower bound for sorting would be fine. Also, any approach (e.g., combinatorial or based on information theory) would be OK. Any suggestions?

$\endgroup$
3
  • 1
    $\begingroup$ What model of computation do you have in mind? If the items are small integers one can do $o(n \log n)$ by sorting. If the items can only be compared for inequality there seems to be a $\Omega(n^2)$ lower bound. Is it correct to infer from the answer you're looking for that the items are linearly ordered and can be compared for <, =, > but no other operations? $\endgroup$ Oct 15, 2010 at 16:02
  • $\begingroup$ Warren’s question in his comment is a good call. Related to this, the comment by David Eppstein on another question is insightful, where he emphasizes the importance of specifying the computational model when we talk about this kind of lower bounds. By the way, I am not sure if it makes sense to list “algebraic computation trees” (a model of computation) and “adversarial arguments” (a proof method) side by side. $\endgroup$ Oct 15, 2010 at 19:16
  • $\begingroup$ Very good points. My application here is explaining about hardness proofs by reduction – for example by reducing from uniqueness to sorting (and several other problems). Therefore, I'm assuming the same basic operations as when working with comparison sorting (so that the reduction will work). (Or, I guess, anything equivalent to the RAM with real numbers.) $\endgroup$ Oct 17, 2010 at 12:04

2 Answers 2

5
$\begingroup$

Any certificate (proof) of distinctness that uses only <, = and > must include comparisons between each pair of adjacent elements in the sorted order. Therefore any certificate of distinctness gives enough information to sort and hence the standard information-theoretic lower bound for sorting applies to any deterministic distinctness algorithm as well.

$\endgroup$
3
  • $\begingroup$ This argument works for comparison trees, but not (directly) for more general decision tree models. $\endgroup$
    – Jeffε
    Oct 15, 2010 at 16:52
  • $\begingroup$ JeffE: I agree. I doubt that there's a simple enough proof for Magnus's purposes that works in a more general model. $\endgroup$ Oct 15, 2010 at 17:01
  • $\begingroup$ Right. Comparison trees is fine for my application – so I guess this is pretty close to what I'm looking for. My application was explaining the idea of hardness proofs, including reducing to sorting, so the fact that the sorting proof is used here sort of short-circuits the whole thing. I guess I should have stated that explicitly :-) $\endgroup$ Oct 17, 2010 at 12:21
8
$\begingroup$

I am not sure if I understand the question correctly, but the proof by Dobkin and Lipton [DL79] that the uniqueness problem on n numbers requires Ω(n log n) comparisons in the linear decision tree model is much easier than the stronger result in the algebraic computation tree model by Ben-Or [Ben83] (not surprisingly).

References

[Ben83] Michael Ben-Or. Lower bounds for algebraic computation trees. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983), pp. 80–86, April 1983. http://doi.acm.org/10.1145/800061.808735

[DL79] David P. Dobkin and Richard J. Lipton. On the complexity of computations under varying sets of primitives. Journal of Computer and System Sciences, 18(1):86–91, Feb. 1979. http://dx.doi.org/10.1016/0022-0000(79)90054-0

$\endgroup$
5
  • 5
    $\begingroup$ In short: Consider the space R^n of all possible inputs. The set of positive inputs has n! connected components, one for each permutation. On the other hand, the subset inputs that can reach any leaf in a linear decision tree is convex, and therefore connected. Thus, any linear decision tree that determines uniqueness has at least n! leaves. $\endgroup$
    – Jeffε
    Oct 15, 2010 at 16:56
  • 5
    $\begingroup$ A more subtle argument is required for the special case of integer inputs. See Lubiw and Rács, "A lower bound for the integer element distinctness problem", Information and Computation 1991; or Yao, "Lower bounds for algebraic computation trees with integer inputs", FOCS 1989. $\endgroup$
    – Jeffε
    Oct 15, 2010 at 16:59
  • 1
    $\begingroup$ @JeffE: Your short explanation is wonderful. Also thank you for the pointer to interesting results. It never occurred to me that the lower bound by Ben-Or does not immediately apply to the case where the input is restricted to integers! $\endgroup$ Oct 15, 2010 at 18:54
  • 1
    $\begingroup$ Jeff: these should be in an answer ! $\endgroup$ Oct 15, 2010 at 19:18
  • $\begingroup$ Thanks to both Tsuyoshi Ito and JeffE. I've seen the R^n space proof before (in a setting using adversarial arguments). I thought it was a bit too complex for my target audience when I first read it, but I guess maybe it isn't, really. Thanks. (I've also seen the paper on the integer case – I think I won't go into that in my lecture… :) $\endgroup$ Oct 17, 2010 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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