An Analysis of Phase Transition in NK Landscapes
  In this paper, we analyze the decision version of the NK landscape model from
the perspective of threshold phenomena and phase transitions under two random
distributions, the uniform probability model and the fixed ratio model. For the
uniform probability model, we prove that the phase transition is easy in the
sense that there is a polynomial algorithm that can solve a random instance of
the problem with the probability asymptotic to 1 as the problem size tends to
infinity. For the fixed ratio model, we establish several upper bounds for the
solubility threshold, and prove that random instances with parameters above
these upper bounds can be solved polynomially. This, together with our
empirical study for random instances generated below and in the phase
transition region, suggests that the phase transition of the fixed ratio model
is also easy.
