Resolen inesperadament un vell problema de la teoria de computació a partir de l'estudi de la covid

Un dels models matemàtics més simples i més utilitzats per descriure epidèmies és l’anomenat model SIR. El model considera la població compartimentada en tres grups: les persones sanes (S), les persones infectades (I) i les persones recuperades i immunes (R). També estipula que hi ha dues transicions possibles entre aquests grups: una té lloc quan una persona sana esdevé una d’infectada perquè s’ha trobat amb una altra que ho estava –ambdues passen a ser persones infectades– i l’altra transició passa quan una persona infectada es recupera.

Aquest model pot ser analitzat matemàticament mitjançant una eina anomenada xarxa de Petri, un tipus de xarxa que compta amb compartiments (els grups de persones) i transicions (els canvis d’un grup a un altre), amb fletxes ponderades per descriure les relacions entre compartiments i transicions (vegeu la figura). A partir de la xarxa de Petri amb els paràmetres que indiquen amb quina taxa s’efectuen les transicions (i que han de ser estimats experimentalment), el model descriu l’evolució dels compartiments i, per tant, de l’epidèmia.

^{Relacions entre els compartiments i les transicions en el model SIR, exemple d’una xarxa de Petri. Els cercles simbolitzen els compartiments, els quadrats representen les transicions possibles i les fletxes indiquen quins compartiments participen en quines transicions. El fet que la primera transició doni lloc a dues persones infectades s’indica a la xarxa de Petri amb el pes 2.}

Quan a l’inici de la pandèmia l’investigador de la UAB Joachim Kock va començar a modelitzar la COVID-19 mitjançant xarxes de Petri, volia experimentar amb la idea de considerar les persones no com a grups estadístics sinó com a individus, una idea inspirada en la informàtica teòrica. En aquest àmbit, les xarxes de Petri consideren un nombre determinat de fitxes a cada compartiment, que es mouen d’acord amb les transicions, de tal manera que una transició pot tenir lloc si hi ha prou fitxes als compartiments d’entrada: es consumeixen fitxes als compartiments d’entrada i se’n produeixen de noves als de sortida.

En la informàtica teòrica, l’ús més important de les xarxes de Petri és com a model de la computació concurrent, però aquest estudi presenta un vell problema encara no resolt des de la dècada de 1980. El problema és que existeixen dues maneres diferents de raonar matemàticament sobre les xarxes de Petri com a model de concurrència, dues «semàntiques», que no s’han pogut reconciliar: una semàntica algebraica i una de geomètrica, amb els seus avantatges i els seus inconvenients.

Simular la COVID-19 amb les xarxes de Petri que s’utilitzen en computació per tal de considerar individus «no va ser una bona idea des del punt de vista de l’epidemiologia», explica Kock, «perquè el formalisme d’aquestes xarxes no permetia traçar les persones individualment. Hi havia una obstrucció, i va resultar ser la mateixa obstrucció que impedia reconciliar les semàntiques algebraica i geomètrica, el vell problema de les xarxes de Petri!».

Per tal de trobar-ne una solució, el professor de la UAB va revisar tota la teoria de les xarxes de Petri i va descobrir que calia modificar-ne lleugerament la mateixa definició per tal que aquestes xarxes admetessin fletxes paral·leles en lloc de pesos, és a dir, passar d’un nombre que representa el pes d’una fletxa a un conjunt de fletxes amb aquest nombre d’elements. «A la teoria d’homotopia, un dels meus camps de recerca, aquest tipus de consideració és habitual», concreta Kock. «En aquest cas, en introduir els conjunts de fletxes apareixen maneres de reordenar-les i simetries que no existeixen si tenim en compte només el pes com a nombre, com la definició convencional». El que faltava a les xarxes de Petri convencionals era exactament l’accés a la informació de les simetries d’una xarxa que proporciona la definició del professor Joachim Kock. «Amb una mica de teoria d’homotopia i teoria de categories, vaig demostrar que la nova versió de les xarxes de Petri admet una reconciliació de les dues semàntiques, l’algebraica i la geomètrica.»

La nova definició proposada per Kock ja ha estat utilitzada per altres investigadors (Evan Patterson i el seu equip a Berkeley, EUA) per desenvolupar un programa informàtic basat en xarxes de Petri per modelitzar epidèmies com la covid. «D’aquesta manera es tanca el cercle. La matemàtica abstracta ha permès transferir coneixements i experiència d’una ciència a una altra, en aquest cas de manera inesperada. Vaig buscar una cosa i he acabat trobant-ne una altra de ben diferent. A vegades és productiu experimentar amb idees que no se sap exactament cap a on et portaran», conclou Kock.

Article de recerca:

J. Kock, Whole-grain Petri Nets and Processes, Journal of the ACM. Volume 70 Issue 1 February 2023 Article No.: 1 pp 1–58 DOI: 10.1145/3559103. https://doi.org/10.1145/3559103