have been used as a prototype and benchmark in the analysis of the performance of different genetic operators and the effects of different encoding methods on the algorithm's performance (Altenberg, 1997; Hordijk, 1997; Jones, 1995).  Kauffman (1993) points out that the parameters that primarily affect a number of ruggedness measures are n and k .

Nevertheless, the fact that for k ≥ 2 the discrete NK landscape is NP-complete (Wright et al., 2000) when the neighbors are arbitrarily chosen could be construed as implying that random landscapes with fixed k are in practice hard.

The results in this paper should serve as a cautionary note that this may not be the case. Our analyses show that for fixed k the uniform probability model is trivially solvable as the problem size tends to infinity. For the fixed ratio model, we have derived two upper bounds for the threshold of the solubility phase transition, and proved that the problem with the control parameter above the upper bounds can be solved in polynomial time with probability asymptotic to 1 due to the existence of easy sub-problems su as 2-SAT. A
series of experiments has also been conducted to investigate the hardness of the problem with the control parameters around and below the threshold. From the experiments, we have observed that the problem is also easy around and below the threshold.

Our proofs hold only for the decision version of the problem where the component functions are discrete on {0,1}. The proofs are obtained by noticing that the clustering of functions, or clauses, on selected subsets of variables implies that the overall problem is decomposable into independent subproblems, or that the problem contains small substructures that identify the solution. The subproblems are the components of the connection graph defined in Section 3 and the 2-SAT sub-problems studied in Section 4.2. It is currently unclear to us to what extent our analysis can be extended to the optimization version of the NK model, and we would like to study this problem further in the future.

In response to the question 'what are the implications for GAs?' we suggest the following speculative line of enquiry. For the discrete model we use, the soluble instances are readily solved by a standard algorithmic approach based on recognizing the components of the connection graph. (This should not be a surprise for us as it has been pointed out by Heckendorn, Rana, and Whitley (1999) that 'Even relatively old algorithms such as Davis- Putnam which are deterministic and exact are orders of magnitude faster than GAs'.) 1 A
similar connectivity can be developed for real valued distributions, for example by capping the minimum value which we allow a sub-function to take.  We can speculate that the clustering imposed by fixed values of k would also generate localized structures when real values are applied and when considering optimization instead of decision, but perhaps with fuzzy boundaries. In fact, this observation is just the flip side of limited epistasis. Genetic algorithms, or their variants such as the probabilistic model-building algorithms (Larranaga & Lozano, 2001), designed to mimic natural evolution, are supposed to take advantage of this situation. So, to the extent that NK landscapes are an accurate reflection of the features exploited by evolutionary algorithms, we pose the following question. Is it possible to identify these fuzzy components if they exist, and in doing so design an algorithm that exploits the same landscape features that the evolutionary algorithms do, but far more efficiently, as we have done for the uniform discrete decision problem?