NP Completeness of Kauffman's N-k Model, A Tuneable 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 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. <p> Key words. rugged fitness landscape, n-k model
Year of publication: |
1996-02
|
---|---|
Authors: | Weinberger, Edward D. |
Institutions: | Santa Fe Institute |
Saved in:
Saved in favorites
Similar items by person
-
Pragmatic Information Rates, Generalizations of the Kelly Criterion, and Financial Market Efficiency
Weinberger, Edward D., (2009)
-
DEPARTMENTS - Book Review: Risk Management
Weinberger, Edward D., (2000)
-
The economy as an evolving complex system
(1988)
- More ...