NK landscapes difficulty and Negative Slope Coefficient: How Sampling
  Influences the Results
  Negative Slope Coefficient is an indicator of problem hardness that has been
introduced in 2004 and that has returned promising results on a large set of
problems. It is based on the concept of fitness cloud and works by partitioning
the cloud into a number of bins representing as many different regions of the
fitness landscape. The measure is calculated by joining the bins centroids by
segments and summing all their negative slopes. In this paper, for the first
time, we point out a potential problem of the Negative Slope Coefficient: we
study its value for different instances of the well known NK-landscapes and we
show how this indicator is dramatically influenced by the minimum number of
points contained into a bin. Successively, we formally justify this behavior of
the Negative Slope Coefficient and we discuss pros and cons of this measure.
