# What computers won't tell you about ecological and evolutionary dynamics

December 09, 2015The authors specifically took a look at complexity theory which is part of theoretical computer science as well as mathematics. It classifies algorithms that can solve certain categories of computational problems according to their inherent difficulty.

They applied these well-defined classes of complexity to some fundamental questions in biology, namely to the ecological and evolutionary dynamics within structured populations. These research questions investigate how population structures affect the outcome of the evolutionary process.

Consider for example the problem of finding the probability that a genetic mutation establishes itself in a resident population, or an invasive species occupies an ecological niche. Though these problems are well studied, an understanding of the computational complexity of even such simple problems was missing.

The investigators found the rather unexpected proof that these fundamental questions in ecology and evolution can be precisely characterized by specific classes of complexity theory, as though these evolutionary processes would mimic aspects of computation. By defining the exact complexity class, they formally proved that these questions cannot be solved with a simple formula.

However, the authors also demonstrated that two classic problems are indeed efficiently solvable: One is the molecular clock--the rate at which neutral mutations accumulate over time--and the other is the exact fixation probability for a genetic variation to take over in the case of a well-mixed population structure.

So how could the researchers tell for certain that some questions are solvable and that an algorithm must exist? And how is it possible to claim that for other specific questions a computational solution is not possible?

The authors used the established methods of computational complexity theory and applied them to the defined evolutionary scenarios in evolutionary game theory and evolutionary graph theory. As a result, they were able to derive the exact complexity class for each of these research questions. The specific complexity class in turn can tell us if an efficient algorithm exists. How so?

For instance, given a gigantic jigsaw puzzle and a guidance telling us where each piece should go, it is easy to assemble the puzzle and check that it indeed gives the picture on the box. Complexity theory calls this type of problems P as the problem can be solved in polynomial time. Among other things, P contains all problems that can be solved with a simple formula. However, many problems cannot be solved in polynomial time as the necessary computational resource would increase exponentially with the growing size of the input. Thus, for such problems, no simple formula exists.

Another important complexity class in the context of this study is nondeterministic polynomial time (NP) which categorizes the problems to which solutions can be verified in polynomial time: If we imagine the giant jigsaw puzzle without the guidance, then it might be hard to decide where some of the pieces should go. However, as mentioned above, once a solution (=guidance) is found it is easy to check that it is indeed a solution.

Incidentally, the question whether all problems in NP belong to P or not is one of the famous six yet unsolved problems of mathematics, for which a Millenium Prize of 1 million dollars was awarded in 2000 by the Clay Mathematics Institute. It is the widely believed albeit yet unproven that P does not equal NP, and hence, the hardest problems in NP cannot be solved with a simple formula.

The findings of the investigators are a first step to establish a connection between the two disciplines of computer science and biology, and they also suggest that research on certain questions in ecological and evolutionary dynamics need to focus on special aspects that can be solved with a simple formula.

-end-

Institute of Science and Technology Austria

**Related Mathematics Articles:**

More democracy through mathematics

For democratic elections to be fair, voting districts must have similar sizes.

For democratic elections to be fair, voting districts must have similar sizes.

How to color a lizard: From biology to mathematics

Skin color patterns in animals arise from microscopic interactions among colored cells that obey equations discovered by Alan Turing.

Skin color patterns in animals arise from microscopic interactions among colored cells that obey equations discovered by Alan Turing.

Mathematics supports a new way to classify viruses based on structure

New research supports a structure-based classification system for viruses which could help in the identification and treatment of emerging viruses.

New research supports a structure-based classification system for viruses which could help in the identification and treatment of emerging viruses.

US educators awarded for exemplary teaching in mathematics

Janet Heine Barnett, Caren Diefenderfer, and Tevian Dray were named the 2017 Deborah and Franklin Tepper Haimo Award winners by the Mathematical Association of America (MAA) for their teaching effectiveness and influence beyond their institutions.

Janet Heine Barnett, Caren Diefenderfer, and Tevian Dray were named the 2017 Deborah and Franklin Tepper Haimo Award winners by the Mathematical Association of America (MAA) for their teaching effectiveness and influence beyond their institutions.

Authors of year's best books in mathematics honored

Prizes for the year's best books in mathematics were awarded to Ian Stewart and Tim Chartier by the Mathematical Association of America (MAA) on Jan.

Prizes for the year's best books in mathematics were awarded to Ian Stewart and Tim Chartier by the Mathematical Association of America (MAA) on Jan.

The mathematics of coffee extraction: Searching for the ideal brew

Composed of over 1,800 chemical components, coffee is one of the most widely-consumed drinks in the world.

Composed of over 1,800 chemical components, coffee is one of the most widely-consumed drinks in the world.

Even physicists are 'afraid' of mathematics

Physicists avoid highly mathematical work despite being trained in advanced mathematics, new research suggests.

Physicists avoid highly mathematical work despite being trained in advanced mathematics, new research suggests.

Mathematics and music: New perspectives on the connections between these ancient arts

World-leading experts on music and mathematics present insights on the connections between these two ancient arts, especially as they relate to composition and performance, as well as creativity, education, and geometry.

World-leading experts on music and mathematics present insights on the connections between these two ancient arts, especially as they relate to composition and performance, as well as creativity, education, and geometry.

Kindergarteners' mathematics success hinges on preschool skills

In a study funded by the National Science Foundation, researchers at the University of Missouri discovered that preschoolers who better process words associated with numbers and understand the quantities associated with these words are more likely to have success with math when they enter kindergarten.

In a study funded by the National Science Foundation, researchers at the University of Missouri discovered that preschoolers who better process words associated with numbers and understand the quantities associated with these words are more likely to have success with math when they enter kindergarten.

First international mathematics research institute launched in Australia

World leaders in the mathematical sciences are visiting Melbourne for a series of research programs at Australia's first international research institute for mathematics and statistics.

World leaders in the mathematical sciences are visiting Melbourne for a series of research programs at Australia's first international research institute for mathematics and statistics.

**Related Mathematics Reading:**

## Best Science Podcasts 2019

We have hand picked the**best science podcasts**for 2019. Sit back and enjoy new science podcasts updated daily from your favorite science news services and scientists.

**Now Playing: TED Radio Hour**

**Anthropomorphic**

Do animals grieve? Do they have language or consciousness? For a long time, scientists resisted the urge to look for human qualities in animals. This hour, TED speakers explore how that is changing. Guests include biological anthropologist Barbara King, dolphin researcher Denise Herzing, primatologist Frans de Waal, and ecologist Carl Safina.

**Now Playing: Science for the People**

**#SB2 2019 Science Birthday Minisode: Mary Golda Ross**

Our second annual Science Birthday is here, and this year we celebrate the wonderful Mary Golda Ross, born 9 August 1908. She died in 2008 at age 99, but left a lasting mark on the science of rocketry and space exploration as an early woman in engineering, and one of the first Native Americans in engineering. Join Rachelle and Bethany for this very special birthday minisode celebrating Mary and her achievements. Thanks to our Patreons who make this show possible! Read more about Mary G. Ross: Interview with Mary Ross on Lash Publications International, by Laurel Sheppard Meet Mary Golda...