Algorithms for determining the maximum of a quadratic 0-1 function, f, over the 2n points of the unit n-dimensional hypercube are often studied by means of test problems in which the data which define f are random numbers. Usually these data are generated randomly and independently from a probability distribution over the integers, symmetric about 0. The general problem is known to be NP-hard; but the algorithms typically depend on the supposition that the number of local maxima is not too large. In this paper, the authors obtain an average case result; namely that when the data are generated as above, subject only to a few minor technical conditions, the expected number of local maxima increases exponentially with n, the dimension of the problem. They show also, how this result is reconciled with a result of Pardalos and Jha that when the test data are generated from a normal distribution, the expected number of local maxima approaches 1 as n⇒•.
