Phase transition in a random NK landscape model

Abstract

An analysis for the phase transition in a random NK landscape model, NK(n, k, z), is given. This model is motivated from population genetics and the solubility problem for the model is equivalent to a random (k +1)-SAT problem. Gao and Culberson [Y. Gao, J. Culberson, An analysis of phase transition in NK landscapes, Journal of Artificial Intelligence Research 17 (2002) 309-332] showed that a random instance generated by NK(n, 2, z) with z > z(0) = 27-7 root 5/4 is asymptotically insoluble. Based on empirical results, they conjectured that the phase transition occurs around the value z = z(0). We prove that an instance generated by NK(n, 2, z) with z < z(0) is soluble with positive probability by providing a polynomial time algorithm. Using branching process arguments, we prove again that an instance generated by NK(n, 2, z) with z > z(0) is asymptotically insoluble. The results show the phase transition around z = z(0) for NK(n, 2, z). In the course of the analysis, we introduce a generalized random 2-SAT formula, which is of self interest, and show its phase transition phenomenon. (C) 2007 Elsevier B.V. All rights reserved.