Black-box complexity: Advantages of memory usage

•Memory restrictions change decision trees to acyclic decision graphs.•Strong advantages for memory size two versus one proved in black-box complexity.•Functions with efficient genetic algorithms but neither with memory size one.

This article proves for the first time the strong advantages of black-box optimizers with storage size two versus one. On the one hand we illustrate for some classes of functions that the black-box complexity for memory size one is exponential. On the other hand these classes are efficiently optimized by black-box algorithms with memory size two and even by simple genetic algorithms.