ABSTRACT Classes of Problems in the Black Box Scenario

The no-free-lunch theorems (NFLTs) do not consider explicitly the structure of problems. This led many researchers to argue that NFLTs cannot be applied to real-world problems (which arguably have structure). However, the notion of structure has never been defined formally and, hence, it is not clear in what way real world problems relate (or not) to the NFLTs and, more generally, to the black box scenario. In [2] we gave a formal definition of structure. We showed that many metaheuristics have identical performance on problems which belong to the same structural class. In this paper, we define a notion of a distance between fitness functions. We argue that an algorithm cannot be efficient on a class of problems if the distance between the fitness function associated with instances of that class is too big. We corroborate our ideas using the following problems: OneMax, trap functions, NIAH, long path, SAT and MAXSAT. 1