Global optima results for the Kauffman NK model

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. Recent NK model results have focused on local optima. This paper analyzes global optima of the NK model. The resulting global optimization problem is transformed into a stochastic network model that is closely related to two well-studied problems in operations research. This leads to applicable strategies for explicit computation of bounds on the global optima particularly with K either small or close to N. A general lower bound, which is sharp for K = 0, is obtained for the expected value of the global optimum of the NK model. A detailed analysis is provided for the expectation and variance of the global optimum when K = N-1. The lower and upper bounds on the expectation obtained for this case show that there is a wide gap between the values of the local and the global optima. They also indicate that the complexity catastrophe that occurs with the local optima does not arise for the global optima.