At 12:28 PM 11/25/1996, Dana W. Albrecht wrote:

For an (again, non-cryptographic) example of a proof of the second sort --- that is, that "any algorithm that solves a given problem requires a minimal running time" --- consider the proof that the "minimal" number of key comparisons in the worst case required to sort a random list of elements for which only an ordering relationship is known is O(nlog(n)). See Knuth, Volume 3, section 5.3. For a simpler example, a standard "binary" search which requires O(log(n)) comparisons to find a given element in the worst case is provably the optimal algorithm for this task.

What is the longest running provably optimal algorithm? Would it be possible to construct a crypto system from it? A relatively weak crypto system which is provably no weaker than it appeared would have its uses.

Comments, anyone?

Congratulations on your excellent post. diGriz