Dana W. Albrecht originally wrote:

Rigorous proofs of the non-existence of an algorithm are not new. Neither are rigorous proofs that any algorithm which can solve a given problem requires a minimal running time. Or, in an even stronger sense,

For a (non-cryptographic) example of a proof of the first sort --- that is, that "there exists no algorithm" --- consider the famous "Halting Problem" for Turing machines. (I believe someone else has also mentioned this.) There are many proofs such as this one, often related, though the Halting Problem itself is perhaps the most famous example.

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.

Dana W. Albrecht (dwa@corsair.com) replies to The Deviant <deviant@pooh-corner.com> like this:

Which part of this have you failed to understand? Look in section 5.3.1 of Volume 3 of "The Art of Computer Programming" by Knuth. You will find there a rigorous proof that the "information theoretic lower bound" of an algorithm which sorts by comparison of keys is O(nlg(n)).

That is a bound on a _reliable_ algorithm. A faster one is to shuffle the elements and present it as sorted. Lightning fast, but only with low probability of correctness. That is what we are up against in a key search attack. The other guy just might guess my 100 bit key first time, millionth time or whatever - early enough anyway. So to get a lower bound you have to show that a lucky guess cannot be distinguished from an unlucky one - and if you do that without a one time pad I take my hat off. -- Peter Allan peter.allan@aeat.co.uk