Phase transition in a random NK landscape model

摘要

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>z0=27−754 is asymptotically insoluble. Based on empirical results, they conjectured that the phase transition occurs around the value z=z0. We prove that an instance generated by NK(n,2,z) with zz0 is asymptotically insoluble. The results show the phase transition around z=z0 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.