Memory-restricted black-box complexity of One Max
We show that the black-box complexity with memory restriction one of the n-dimensional ONEMAX function class is at most 2n. This disproves the Theta(n logn) conjecture of Droste, Jansen, and Wegener (Theory Computing Systems 39 (2006) 525-544). (C) 2011 Elsevier B.V. All rights reserved.
black-box complexity algorithms query complexity bounded memory