NP Completeness of Kauffman’s N-k Model, a Tuneably Rugged Fitness Landscape

The concept of a “fitness landscape,” a picturesque term for a mapping of the vertices of a finite graph to the real numbers, has arisen in several fields, including evolutionary theory. The computational complexity of two, qualitatively similar versions of a particularly simple fitness landscape are shown to differ considerably. In one version, the question “Is the global optimum greater than a given value ${\cal V}$?” is shown to be answerable in polynominal time by presenting an efficient algorithm that actually computes the optimum. The corresponding problem for the other version of the landscape is shown to be ${\cal NP}$ complete. The ${\cal NP}$ completeness of the latter problem leads to some speculations on why ${\cal P} \neq {\cal NP}$.