The unbiased black-box complexity of partition is polynomial

Unbiased black-box complexity was introduced as a refined complexity model for random-ized search heuristics (Lehre and Witt (2012) [24]). For several problems, this notion avoids the unrealistically low complexity results given by the classical model of Droste et al. (2006) [10]. We show that for some problems the unbiased black-box complexity remains artificially small. More precisely, for two different formulations of an NP-hard subclass of the well-known Partition problem, we give mutation-only unbiased black-box algorithms having complexity O(nlog n). This indicates that also the unary unbiased black-box complexity does not give a complete picture of the true difficulty of this problem for randomized search heuristics.