# 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:**

Could mathematics help to better treat cancer?

Impaired information processing may prevent cells from perceiving their environment correctly; they then start acting in an uncontrolled way and this can lead to the development of cancer.

Impaired information processing may prevent cells from perceiving their environment correctly; they then start acting in an uncontrolled way and this can lead to the development of cancer.

People can see beauty in complex mathematics, study shows

Ordinary people see beauty in complex mathematical arguments in the same way they can appreciate a beautiful landscape painting or a piano sonata.

Ordinary people see beauty in complex mathematical arguments in the same way they can appreciate a beautiful landscape painting or a piano sonata.

Improving geothermal HVAC systems with mathematics

Sustainable heating, ventilation, and air conditioning systems, such as those that harness low-enthalpy geothermal energy, are needed to reduce collective energy use and mitigate the continued effects of a warming climate.

Sustainable heating, ventilation, and air conditioning systems, such as those that harness low-enthalpy geothermal energy, are needed to reduce collective energy use and mitigate the continued effects of a warming climate.

How the power of mathematics can help assess lung function

Researchers at the University of Southampton have developed a new computational way of analyzing X-ray images of lungs, which could herald a breakthrough in the diagnosis and assessment of chronic obstructive pulmonary disease (COPD) and other lung diseases.

Researchers at the University of Southampton have developed a new computational way of analyzing X-ray images of lungs, which could herald a breakthrough in the diagnosis and assessment of chronic obstructive pulmonary disease (COPD) and other lung diseases.

Mathematics pushes innovation in 4-D printing

New mathematical results will provide a potential breakthrough in the design and the fabrication of the next generation of morphable materials.

New mathematical results will provide a potential breakthrough in the design and the fabrication of the next generation of morphable materials.

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.

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.

## Top Science Podcasts

We have hand picked the**top science podcasts of 2019**.

**Now Playing: TED Radio Hour**

**In & Out Of Love**

We think of love as a mysterious, unknowable force. Something that happens to us. But what if we could control it? This hour, TED speakers on whether we can decide to fall in â and out of â love. Guests include writer Mandy Len Catron, biological anthropologist Helen Fisher, musician Dessa, One Love CEO Katie Hood, and psychologist Guy Winch.

**Now Playing: Science for the People**

**#542 Climate Doomsday**

Have you heard? Climate change. We did it. And it's bad. It's going to be worse. We are already suffering the effects of it in many ways. How should we TALK about the dangers we are facing, though? Should we get people good and scared? Or give them hope? Or both? Host Bethany Brookshire talks with David Wallace-Wells and Sheril Kirschenbaum to find out. This episode is hosted by Bethany Brookshire, science writer from Science News. Related links: Why Climate Disasters Might Not Boost Public Engagement on Climate Change on The New York Times by Andrew Revkin The other kind...