NP Completeness of Kauffman's N-k Model, A Tuneable Rugged Fitness Landscape

Edward Weinberger

Working Papers from Santa Fe Institute

Abstract: 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.

Key words. rugged fitness landscape, n-k model

Date: 1996-02
References: View complete reference list from CitEc
Citations: View citations in EconPapers (9)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:96-02-003

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().