Computational complexity of ecological and evolutionary spatial dynamics
Open accessThe DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Abstract
Significance: An important question in evolution is: how does population structure affect the outcome of the evolutionary process? The theory of evolution in structured population has provided an impressive range of results, but an understanding of the computational complexity of even simple questions was missing. We prove that some fundamental problems in ecology and evolution can be precisely characterized by well-established computational complexity classes. This implies that the problems cannot be answered by simple equations. For example, there cannot be simple formulas for the fixation probability of a mutant given frequency-dependent selection in a structured population. We also show that, for example, calculating the molecular clock of neutral evolution in structured populations admit efficient algorithmic solutions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Evolutionary Games and Population Dynamics
Hofbauer, J., & Sigmund, K. (1998) · doi:10.1017/cbo9781139173179 · Cited by 5,502
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705 · cited 2×
“In a bipartite graph G , the vertex set V is partitioned into vertices V vertices) and V (right vertices) and all edges go from a vertex in Given a bipartite graph, the problem of computing the number of distinct perfect matchings was shown by Valiant [16] to be Uniform degree property.”
Evolutionary Dynamics: Exploring the Equations of Life
NOWAK, M. A. (2006) · doi:10.2307/j.ctvjghw98 · Cited by 2,438
Self-citationA simple rule for the evolution of cooperation on graphs and social networks
Ohtsuki, H., Hauert, C., Lieberman, E., & Nowak, M. A. (2006) · Nature · doi:10.1038/nature04605 · Cited by 2,208
Self-citationCoevolution of Strategy and Structure in Complex Networks with Dynamical Linking
Pacheco, J. M., Traulsen, A., & Nowak, M. A. (2006) · Physical Review Letters · doi:10.1103/physrevlett.97.258103 · Cited by 697
Self-citationReputation-based partner choice promotes cooperation in social networks
Fu, F., Hauert, C., Nowak, M. A., & Wang, L. (2008) · Physical Review E · doi:10.1103/physreve.78.026117 · Cited by 682
Self-citationDynamic social networks promote cooperation in experiments with humans
Rand, D. G., Arbesman, S., & Christakis, N. A. (2011) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1108243108 · Cited by 653
Strategy selection in structured populations
Tarnita, C. E., Ohtsuki, H., Antal, T., Fu, F., & Nowak, M. A. (2009) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2009.03.035 · Cited by 281
Self-citation
Cited by
Evolutionary dynamics on any population structure
Allen, B., Lippner, G., Chen, Y.-T., Fotouhi, B., Momeni, N., Yau, S.-T., & Nowak, M. A. (2017) · Nature · doi:10.1038/nature21723 · Cited by 534
Self-citationSocial goods dilemmas in heterogeneous societies
McAvoy, A., Allen, B., & Nowak, M. A. (2020) · Nature Human Behaviour · doi:10.1038/s41562-020-0881-2 · Cited by 94
“Analytical calculations for stronger selection (larger δ) quickly become infeasible for arbitrary heterogeneous graphs Ibsen-Jensen et al. (2015), but remain tractable for structures with a high degree of symmetry, such as the star (Hadjichrysathou et al.”
BackgroundSelf-citationA mathematical formalism for natural selection with arbitrary spatial and genetic structure
Allen, B., & McAvoy, A. (2019) · Journal of Mathematical Biology · doi:10.1007/s00285-018-1305-z · Cited by 37
Evaluating the structure-coefficient theorem of evolutionary game theory
McAvoy, A., & Wakeley, J. (2022) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2119656119 · Cited by 23
“Outside of the realm of weak selection, there need not be any efficient algorithm for evaluating a population’s evolutionary dynamics in general (79), a conclusion that has prompted other kinds of computational techniques, such as the development of more efficient algorithms for numerical simulation (44).”
Background
Metadata
- Authors
- Ibsen-Jensen, R., Chatterjee, K., & Nowak, M. A.
- Venue
- Proceedings of the National Academy of Sciences
- Published
- 2015-12-07
- Volume
- 112
- Issue
- 51
- Pages
- 15636-15641
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W2194397134
- Cited by
- 66
- References
- 12
- FWCI
- 5.50
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Computational complexity of ecological and evolutionary spatial dynamics. https://app.cochat.ai/papers/10.1073/pnas.1511366112
- The paper
- Ibsen-Jensen, R., Chatterjee, K., & Nowak, M. A. (2015). Computational complexity of ecological and evolutionary spatial dynamics. Proceedings of the National Academy of Sciences. https://doi.org/10.1073/pnas.1511366112
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.