The Unrestricted Black-Box Complexity of Jump Functions

We analyze the unrestricted black-box complexity of the JUMP function classes for different jump sizes. For upper bounds, we present three algorithms for small, medium, and extreme jump sizes. We prove a matrix lower bound theorem which is capable of giving better lower bounds than the classic information theory approach. Using this theorem, we prove lower bounds that almost match the upper bounds. For the case of extreme jump functions, which apart from the optimum reveal only the middle fitness value(s), we use an additional lower bound argument to show that any black-box algorithm does not gain significant insight about the problem instance from the first Ω(√en) fitness evaluations. This, together with our upper bound, shows that the black-box complexity of extreme jump functions is n + Θ(√ n).