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$
  • 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$ – Warren Schudy Oct 15 '10 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$ – Tsuyoshi Ito Oct 15 '10 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$ – Magnus Lie Hetland Oct 17 '10 at 12:04
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$
  • $\begingroup$ This argument works for comparison trees, but not (directly) for more general decision tree models. $\endgroup$ – Jeffε Oct 15 '10 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$ – Warren Schudy Oct 15 '10 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$ – Magnus Lie Hetland Oct 17 '10 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
    $\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 '10 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 '10 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$ – Tsuyoshi Ito Oct 15 '10 at 18:54
  • 1
    $\begingroup$ Jeff: these should be in an answer ! $\endgroup$ – Suresh Venkat Oct 15 '10 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$ – Magnus Lie Hetland Oct 17 '10 at 12:09

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.