Format

Send to

Choose Destination
Proc Natl Acad Sci U S A. 2014 Nov 11;111(45):15881-7. doi: 10.1073/pnas.1416954111. Epub 2014 Oct 27.

Algorithms, complexity, and the sciences.

Author information

1
Simons Institute for the Theory of Computing, University of California, Berkeley, CA 94720 christos@berkeley.edu.

Abstract

Algorithms, perhaps together with Moore's law, compose the engine of the information technology revolution, whereas complexity--the antithesis of algorithms--is one of the deepest realms of mathematical investigation. After introducing the basic concepts of algorithms and complexity, and the fundamental complexity classes P (polynomial time) and NP (nondeterministic polynomial time, or search problems), we discuss briefly the P vs. NP problem. We then focus on certain classes between P and NP which capture important phenomena in the social and life sciences, namely the Nash equlibrium and other equilibria in economics and game theory, and certain processes in population genetics and evolution. Finally, an algorithm known as multiplicative weights update (MWU) provides an algorithmic interpretation of the evolution of allele frequencies in a population under sex and weak selection. All three of these equivalences are rife with domain-specific implications: The concept of Nash equilibrium may be less universal--and therefore less compelling--than has been presumed; selection on gene interactions may entail the maintenance of genetic variation for longer periods than selection on single alleles predicts; whereas MWU can be shown to maximize, for each gene, a convex combination of the gene's cumulative fitness in the population and the entropy of the allele distribution, an insight that may be pertinent to the maintenance of variation in evolution.

KEYWORDS:

complexity of equilibria; lens of computation; multiplicative weights update

Supplemental Content

Full text links

Icon for HighWire Icon for PubMed Central
Loading ...
Support Center