Algorithms, complexity, and the sciences

Por • 29 ago, 2021 • Sección: Opinion

Christos Papadimitriou

Significance

The theory of algorithms and complexity, of which the basic concepts and results are being reviewed here, is an important and consequential domain of mathematical investigation that is unfamiliar to most PNAS readers. Furthermore, in the second half of the article we focus on recent and current research, applying these concepts and results to help elucidate certain central theoretical problems in the social and life sciences, including market equilibria and the theory of evolution.

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.

See all authors and affiliations

PNAS November 11, 2014 111 (45) 15881-15887; first published October 27, 2014; https://doi.org/10.1073/pnas.1416954111

Contributed by Christos Papadimitriou, September 12, 2014 (sent for review July 20, 2014; reviewed by Avi Wigderson and Jon Kleinberg)

https://www.pnas.org/content/111/45/15881

Post to Twitter

Escribe un comentario