The usual way of stating the No Free Lunch Theorem involves an ``uninformative'' prior over search problems, rather than an Adversary. But the latter formulation is equivalent if not stronger, and naturally I prefer the (so to speak) de-Bayesed version. See Joseph C. Culberson, ``On the Futility of Blind Search: An Algorithmic view of `No Free Lunch','' Evolutionary Computation