---
_id: '1559'
abstract:
- lang: eng
text: 'There are deep, yet largely unexplored, connections between computer science
and biology. Both disciplines examine how information proliferates in time and
space. Central results in computer science describe the complexity of algorithms
that solve certain classes of problems. An algorithm is deemed efficient if it
can solve a problem in polynomial time, which means the running time of the algorithm
is a polynomial function of the length of the input. There are classes of harder
problems for which the fastest possible algorithm requires exponential time. Another
criterion is the space requirement of the algorithm. There is a crucial distinction
between algorithms that can find a solution, verify a solution, or list several
distinct solutions in given time and space. The complexity hierarchy that is generated
in this way is the foundation of theoretical computer science. Precise complexity
results can be notoriously difficult. The famous question whether polynomial time
equals nondeterministic polynomial time (i.e., P = NP) is one of the hardest open
problems in computer science and all of mathematics. Here, we consider simple
processes of ecological and evolutionary spatial dynamics. The basic question
is: What is the probability that a new invader (or a new mutant)will take over
a resident population?We derive precise complexity results for a variety of scenarios.
We therefore show that some fundamental questions in this area cannot be answered
by simple equations (assuming that P is not equal to NP).'
author:
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Ibsen-Jensen R, Chatterjee K, Nowak M. Computational complexity of ecological
and evolutionary spatial dynamics. PNAS. 2015;112(51):15636-15641. doi:10.1073/pnas.1511366112
apa: Ibsen-Jensen, R., Chatterjee, K., & Nowak, M. (2015). Computational complexity
of ecological and evolutionary spatial dynamics. PNAS. National Academy
of Sciences. https://doi.org/10.1073/pnas.1511366112
chicago: Ibsen-Jensen, Rasmus, Krishnendu Chatterjee, and Martin Nowak. “Computational
Complexity of Ecological and Evolutionary Spatial Dynamics.” PNAS. National
Academy of Sciences, 2015. https://doi.org/10.1073/pnas.1511366112.
ieee: R. Ibsen-Jensen, K. Chatterjee, and M. Nowak, “Computational complexity of
ecological and evolutionary spatial dynamics,” PNAS, vol. 112, no. 51.
National Academy of Sciences, pp. 15636–15641, 2015.
ista: Ibsen-Jensen R, Chatterjee K, Nowak M. 2015. Computational complexity of ecological
and evolutionary spatial dynamics. PNAS. 112(51), 15636–15641.
mla: Ibsen-Jensen, Rasmus, et al. “Computational Complexity of Ecological and Evolutionary
Spatial Dynamics.” PNAS, vol. 112, no. 51, National Academy of Sciences,
2015, pp. 15636–41, doi:10.1073/pnas.1511366112.
short: R. Ibsen-Jensen, K. Chatterjee, M. Nowak, PNAS 112 (2015) 15636–15641.
date_created: 2018-12-11T11:52:43Z
date_published: 2015-12-22T00:00:00Z
date_updated: 2021-01-12T06:51:36Z
day: '22'
department:
- _id: KrCh
doi: 10.1073/pnas.1511366112
external_id:
pmid:
- '26644569'
intvolume: ' 112'
issue: '51'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4697423/
month: '12'
oa: 1
oa_version: Submitted Version
page: 15636 - 15641
pmid: 1
publication: PNAS
publication_status: published
publisher: National Academy of Sciences
publist_id: '5612'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computational complexity of ecological and evolutionary spatial dynamics
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2015'
...