During the Covid-19 pandemic, many of us have become amateur mathematicians. How fast will hospitalizations grow and when will herd immunity be achieved?Professional mathematicians are also challenged, University of Copenhagen researchers solve his 30-year-old problem in computer science I got the idea to do it.Breakthrough published by authoritative Journal of the ACM (Association for Computing Machinery).
“Like many others, I was calculating how epidemics would develop. In this context, I wanted to investigate certain ideas from theoretical computer science. , I realized that the big problem is that there is no solution to an old problem,” says Joachim Kock, associate professor of mathematics at the University of Copenhagen.
His solution to this problem could be useful not only in epidemiology and computer science, but also in other fields. A common feature of these disciplines is the existence of systems in which various components influence each other. For example, if a healthy person met her COVID-infected person, she could infect two people as a result.
A clever method invented by a German teenager
To understand this breakthrough, we need to know that such complex systems can be described mathematically by so-called Petri nets. This method was invented in 1939 by his Carl Adam Petri in Germany (when he was 13 by the way) for chemical applications. Just like a healthy person sees her COVID-infected person, the same thing can happen when two chemicals mix and react.
In a Petri net, various components are drawn as circles, and events such as chemical reactions and infections are drawn as squares. Then connect the circles and squares with arrows that indicate interdependencies within the system.
A simplified version of the petri net for COVID infection. The starting point is an uninfected person. “S” stands for “susceptibility”. Contact with an infected person (“I”) is an event that leads to two infected persons. Another event later occurs, removing a person from the group of infected. Here ‘R’ means ‘recovery’, which in this context can be healing or dying. Either outcome removes the person from the infected group.
computer scientists deemed the problem unsolvable
In chemistry, Petri nets are applied to calculate how the concentrations of various chemicals in a mixture change. This idea has influenced the use of Petri nets in other fields such as epidemiology. We started with a high ‘concentration’ of uninfected people and then the ‘concentration’ of infected people is starting to rise. In computer science, Petri his net use is somewhat different. The focus is on individuals rather than concentration, and development is gradual rather than continuous.
What Joachim Kock had in mind was to apply computer science’s more person-oriented Petri nets to the calculation of COVID. This is when he ran into an old problem.
“Basically, the process of a Petri net can be described by two separate approaches. I see it as a graphical representation,” said Joachim Kock, adding:
“The serial approach is well-suited for performing computations. However, it has the disadvantage that causal relationships cannot be explained more accurately than the graphical approach. tends to be.”
“The problem is that no one has been able to integrate the two approaches. Computer scientists have more or less resigned, seeing the problem as unsolvable. No one knew we needed to fix it,” says Joachim Kock.
Small change, big impact
Danish mathematicians realized that a small change in the definition of a Petri net could solve the problem.
“Instead of just counting and writing numbers, by allowing parallel arrows, Additional information becomes available. Things are going well and you can combine the two approaches. ”
The exact mathematical reasons why this additional information is important are complex, but can be explained by analogy.
“Assigning numbers to things has helped mankind a lot. It’s very practical.However, the number of chairs and guests doesn’t tell you who will sit where.When you consider numbers instead of real objects, you lose some information.”
Similarly, information is lost when individual arrows in a Petri net are replaced by numbers.
“It’s a bit more work to deal with the parallel arrows individually, but it pays off well as it lets you combine the two approaches and get the benefits of both at the same time.”
Circle to COVID closed
According to Joachim Kock, the solution is useful for mathematically understanding how to describe complex systems with many interdependencies, but it is not very relevant to the day-to-day work of computer scientists using Petri nets. No effect.
“This is because the necessary changes are mostly backwards compatible and can be applied without having to modify the entire Petri net theory.”
“Somewhat surprisingly, some epidemiologists have started using a revised Petri net. So you might say the circle is closed!
Joachim Kock sees further points in this story.
“I never set out to find a solution to an old problem in computer science. I just wanted to do the COVID math. Therefore, I would like to take this opportunity to highlight the importance of research without a specific purpose: research driven by curiosity can lead to breakthroughs.”
