--- _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' ...