phase transition in a random nk landscape model
An analysis for the phase transition in a random NK landscape model is given. For the fixed ratio model, NK( n , k , z ), Gao and Culberson [17] showed that a random instance generated by NK( n ,2, z ) with z > z 0 = 27-7/?54 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 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.
phase transition nk landscape random  k -sat problem unit clause algorithm branching process