Complexity of the predecessor problem in Kauffman networks
S. N. Coppersmith · Physical Review E · 2007
Kauffman nets, also known as N-K models, have been studied extensively because their dynamics can be used to model a variety of interesting dynamical processes. This paper investigates the properties of the problem of determining whether or not a given configuration of a Kauffman net has a predecessor. Here it is shown that when the parameter K that governs the number of connections grows as ln(N) , where N is the number of elements, the problem of finding a solution is extremely sensitive to small changes in the problem statement. This result has implications for studies of the physics of random systems and also may have applications for questions in computational complexity theory.