Too fast unbiased black-box algorithms

Unbiased black-box complexity was recently introduced as a refined complexity model for randomized search heuristics (Lehre and Witt, GECCO 2010). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste, Jansen, and Wegener (Theor. Comput. Sci. 2006). In this work, we show that for two natural problems the unbiased black-box complexity remains artificially small. For the classical Jump _k test function class and for a subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity O(n log n). Since the first problem usually needs θ(n ^k) function evaluations to be optimized by standard heuristics and the second is even NP-complete, these blackbox complexities seem not to indicate the true difficulty of the two problems for randomized search heuristics.