cads: i don't see it because regardless of the supposed usefullness, the algorithm still uses 2^k energy.

cads: mircea_popescu: it's without question that anyone can look at the outputs of the two algorithms and verify that ~2^k energy was expended. Perhaps the problem happens when we require the second algorithm to also guarantee a useful output relative to the third party.

cads: let me offer a counter "you can solve a partial hash collision problem (something like an O(2^k) expected running time), or you can solve a np-complete problem requiring brute searching a binary tree of height k (assume similar expected chance of success)."