

![0_image_0.png](0_image_0.png)

obvious that the original 3-SAT problem ϕ is satisfiable only if the 2-SAT sub-problem ϕ is stisfiable. In the experiment, we generate instances of the NK landscape N(n, 2, z), convert them to the equivalent 3-SAT problems, and extract the 2-SAT sub-problems. These 2-SAT
problems are then solved by the relsat solver. If the 2-SAT problem is unsatisfiable, then the original NK landscape instance is also insoluble.

The experimental settings are the same as those in the experiment on the original problem. The results are shown in Figures 3-4, in parallel to the Figures 1-2 of the results on the original 3-SAT problems in Section 5.1.  We see that the patterns of insoluble fractions and search cost are similar to those we found in the original 3-SAT problems. There is a soluble-insoluble phase transition occurring around 2.83, but the fraction of unsatisfiable instances is lower than the fraction in the original 3-SAT problems.

We also observed that the average search cost for the 2-SAT sub-problems remains the same as that for the original 3-SAT problems. This tells us that the difficulty of solving a soluble instance of NK landscape is almost the same as that of solving a 2-SAT problem, and hence is easy. Therefore, on average the NK landscape N(n, 2, z) is also easy at parameters below the threshold where almost all of the instances are soluble.

## 6. Implications And Conclusions

One of the questions that arises about this work is its implications to the design and analysis of genetic algorithms.  NK landscapes were initially conceived as simplified models of evolutionary landscapes which could be tuned with respect to ruggedness and epistatic interactions (Kauffman, 1989). In the study of genetic algorithms, NK landscape models