Landscape statistics of the low-autocorrelation binary string problem

The statistical properties of the energy landscape of the low-autocorrelation binary string problem (LABSP) are studied numerically and compared with those of several classic disordered models. Using two global measures of landscape structure which have been introduced in the simulated annealing literature, namely, depth and difficulty, we find that the landscape of the LABSP, except perhaps for a very large degeneracy of the local minimum energies, is qualitatively similar to some well known landscapes such as that of the mean-field two-spin glass model. Furthermore, we show both analytically and numerically that a well known mean-field approximation to the pure model describes the statistical properties of the LABSP extremely well.