NP Completeness of Kauffman's N-k Model, A Tuneable Rugged Fitness Landscape
Edward D. Weinberger · RePEc: Research Papers in Economics · 1996
The concept of a 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 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 NP complete. The NP completeness of the latter problem leads to some speculations on why P not equal to NP. Key words. rugged fitness landscape, n-k model