Eli, most of what you say above isn't new to me -- I've already encountered these things in my work on defining machine intelligence. Moreover, none of this has much impact on the fact that measuring the power of an optimiser simply in terms of the relative size of a target subspace to the search space doesn't work: sometimes tiny targets in massive spaces are trivial to solve, and sometimes bigger targets in moderate spaces are practically impossible. The simple number-of-bits-of-optimisation-power method you describe in this post doesn't take this into account. As far as I can see, the only way you could deny this is if you were a strong NFL theorem believer.