This is just wrong,,,

[compilerbitch]

Moved here from a conversation under a locked post, because it's too interesting to hide. (Thanks to lethargic_man)...

From http://www.no-free-lunch.org/ :

Wolpert and Macready (1995), "No Free Lunch Theorems for Search"
"...all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions. In particular, if algorithm A outperforms algorithm B on some cost functions, then loosely speaking there must exist exactly as many other functions where B outperforms A."

Wolpert and Macready (1997), "No Free Lunch Theorems for Optimization"
"...for any algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class."

My reply earlier:

I have a slight problem with what I read on the 'no free lunch' site, because the argument (at least as regards computational complexity) seems to have a big hole in it that goes something like this:

A and B are both (deterministic) search algorithms operating on the same problem. Search time 'area under the curve' is equal in both cases, but O(A x) will typically differ from O(B x), for most x [EDIT: assume here that there exists an x and y such that O(A x) < O(B x) and O(A y) > O(B y) -- this trick doesn't apply if A is always better than B or vice-versa]. Let A|B be a composite algorithm, constructed by composing A and B in parallel (perhaps running on two separate processors, or as two fairly scheduled threads) such that (A|B) x returns a result as soon as the first of A or B returns a result, with the other (redundant) process being terminated immediately. It follows trivially that for all x, O((A|A) x) = O(A x), O((A|B) x) <= O(A x) and O((A|B) x) <= O(B x), so, strictly, A|B has better complexity than either A or B acting alone (assuming that O(A x) does not equal O(B x) for some x).

This would seem to be a trivial disproof by counterexample. A similar counterexample should also hold for quality of results in suboptimal optimisation (e.g. if P and Q generate results p = P x and q = Q x for some x, optimised against some cost function C, pick the best of p and q, so (to invent a bit more notation), C((P||Q) x) <= C(P x) and C((P||Q) x) <= C(Q x) for all x. Amortising this over the whole domain would inevitably show that the composite function is better than either of the original functions iff there exists at least one x where P x is not equal to Q x -- for the lattice theory pedants out there, I should probably mention also that all (some?) members of the range of C must be comparable).

Maybe there are still no free lunches, but it should be reasonable to go looking for free coffee refills, at least. :-)

Comments

[compilerbitch.livejournal.com]

I think it's basically down to the very simplistic idea that if you have N possible results, choosing an order in which to search through those results makes no difference to overall complexity iff at some point you have to enumerate every possible result in order to find the one you're looking for. Put another way, it's the needle-in-a-haystack problem -- it doesn't matter where in the haystack you start looking, because the needle could be anywhere in there. This, at first sight, looks like a really solid and reliable result, but it makes the assumption that there is *exactly one* needle, that there is nowhere that needles are usually found, and that you don't own a metal detector. :-)

Applying this argument to optimisation problems with multiple possible optimal results (as in SAT), or with large numbers of suboptimal but still useful results (as in GAs or MAXSAT, a variant of SAT where you're happy if you get close rather than all the way to a result), doesn't apply, which is demonstrated by the counter example I posted.

It's a case of someone coming up with something that looks and feels very fundamental, and that you can do proofs about, then having the idea applied to related problems with different underlying assumptions and then ending up with something entirely bogus.