Kauffman & Levin, 1987 — turning "ruggedness" into a knob you can turn
Some problems yield to patient incremental change until you reach the best answer. Others stall at some point and refuse to move again, while you know perfectly well a better solution exists elsewhere. What separates the two?
Once configuration space is drawn as terrain, the question becomes: what sets the ruggedness of a landscape — how many peaks it has, and how far apart they sit? What Kauffman and Levin wanted was not the true landscape of any particular system (usually unmeasurable) but a generator with an adjustable ruggedness dial: one knob that runs continuously from "a single mountain" to "completely random rubble". Only with that in hand can you ask how search behaviour changes as ruggedness changes.
Everything hangs on rules 2 and 3. K is the degree of interdependence: at K = 0 each component decides its own fate; at K = N−1 every component's contribution is held hostage by all the others. The random draw is deliberate — it encodes "we know nothing about the nature of these dependencies", so the only information entering the model is K itself.
One consequence is worth stating plainly: flipping one component changes not only its own contribution but the contributions of every component that depends on it, roughly K of them. The larger K, the more a single change scrambles — and that is where ruggedness comes from.
Start from a random configuration and keep moving to a better neighbour — an adaptive walk — until no better neighbour exists. Three things show up reliably.
① At K = 0 the landscape has one mountain. Each component's best state is independent of the others, so you can settle them one at a time and every starting point leads to the same summit. That summit's fitness is the average of "better of two draws" per component, about 0.67, and reaching it takes around N/2 steps.
② At K = N−1 the landscape is fully random. The fitnesses of adjacent configurations are unrelated. Here the number of local optima is 2N⁄(N+1) — about fifty thousand at N = 20. Worse, the walk ends quickly: with each step upward the number of still-better neighbours roughly halves, so from a random start you stall after on the order of log₂N steps. A system with N = 100 gets stuck after about seven.
③ And where it stalls is not high. The larger K, the closer the peaks reachable by adaptive walks sit to 0.5, the average of random configurations. Kauffman named this the complexity catastrophe: past a certain degree of mutual constraint between components, evolution or optimisation stops conferring much advantage at all.
A frequently overlooked result sits between the extremes: at intermediate K the landscape has many peaks while retaining correlation between them (the correlation length shortens as K rises). Moderate K is the only band where good solutions are both diverse and still findable by search — the closest thing the NK vocabulary offers to a definition of "the edge of chaos".
The NK model is never used by plugging real data in and computing an answer. It is a machine for generating qualitative expectations: if the components of some system become more interdependent, what should you see?
Its expectations are quite specific. Local optima multiply — different teams, species or firms settle stably on different solutions, none of them optimal. Returns to incremental search decay fast: the same effort buys smaller and smaller improvements. Starting point matters more than effort (path dependence). And imitation becomes hard — Jan Rivkin argued exactly this with NK in 2000: a high-K strategy resists copying even when fully visible, because getting one or two components wrong drops you into a valley, and the number of components makes exhaustive search infeasible.
The same machine explains why modularity is such a common evolutionary product. Carving a system into modules is deliberately pushing K down; the price is giving up cross-module synergy (a slightly lower peak), and the purchase is that small improvements start working again. It is the quantitative version of the near-decomposability argument in Topic 3.