These landscapes were designed with the intent of studying limited interactions, and our results can also be seen as a confirmation that indeed limited epistasis leads to easier problems. In another domain, that of the more traditional research into search and optimization, there is a need for test bed problems with real world connections which are tunable with respect to difficulty. NK landscapes might have been such a domain for generating 3-SAT
instances. It is disappointing that for restricted k the instances generated are easy with high probability.

## Acknowledgments

This research supported in part by Natural Sciences and Engineering Research Council Grant No. OGP8053. We thank the anonymous reviewers for their comments.

## References

Achlioptas, D. (1999). Threshold Phenomena in Random Graph Colouring and Satisfiability . Ph.D. thesis, Department of Computer Science, University of Toronto, Toronton, Canada.

Achlioptas, D. (2001). A survey of lower bounds for random 3-sat via differential equations.

Theoretical Computer Science, 265, 159-185.

Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., & Molloy, M. (1997). Random constraint satisfaction: A more accurate picture. In Proceedings of CP97, pp. 107–
120. Springer.

Alon, N., & Spencer, J. (1992). The Probabilistic Method. Wiley, New York.

Altenberg, L. (1997). Nk fitness landscapes. In Back, T., Fogel, D., & Michalewicz, Z.

(Eds.), Handbook of Evolutionary Computation. Oxford University Press, New York.

Cheeseman, P., Kanefsky, B., & Taylor, W. (1991). Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, pp.

31–337. Morgan Kaufmann.

Cook, S., & Mitchell, D. (1997). Finding hard instances of the satisfiability problem: A
survey. In Du, Gu, & Pardalos (Eds.), Satisfiability Problem: Theory and Applications, Vol. 35 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science.

American Mathematical Society.

Culberson, J., & Gent, I. (2001). Frozen development in graph coloring. Theoretical Computer Science, 265 (1-2), 227–264.

Dubois, O. (2001). Upper bounds on the satisfiability threshold. Theoretical Computer Science, 265 (1-2), 187–197.

Franco, J., & Gelder, A. (1998). A perspective on certain polynomial time solvable classes of satisfiability. Discrete Applied Mathematics, to appear.

Franco, J., & Paul, M. (1983). Probabilistic analysis of the davis-putnam procedure for solving satisfiability. Discrete Applied Mathematics, 5, 77-87.