Polynomial Equivalence of Extended Chemical Reaction Models
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918144217448448 |
|---|---|
| author | Bajaj, Divya Castellanos, Jose Luis Knobel, Ryan Luchsinger, Austin Massie, Aiden Salinas, Adrian Santos, Pablo Santos, Ramiro Schweller, Robert Wylie, Tim |
| author_facet | Bajaj, Divya Castellanos, Jose Luis Knobel, Ryan Luchsinger, Austin Massie, Aiden Salinas, Adrian Santos, Pablo Santos, Ramiro Schweller, Robert Wylie, Tim |
| contents | The ability to detect whether a species (or dimension) is zero in Chemical Reaction Networks (CRN), Vector Addition Systems, or Petri Nets is known to increase the power of these models -- making them capable of universal computation. While this ability may appear in many forms, such as extending the models to allow transitions to be inhibited, prioritized, or synchronized, we present an extension that directly performs this zero checking. We introduce a new void genesis CRN variant with a simple design that merely increments the count of a specific species when any other species' count goes to zero. As with previous extensions, we show that the model is Turing Universal. We then analyze several other studied CRN variants and show that they are all equivalent through a polynomial simulation with the void genesis model, which does not merely follow from Turing-universality. Thus, inhibitor species, reactions that occur at different rates, being allowed to run reactions in parallel, or even being allowed to continually add more volume to the CRN, does not add additional simulation power beyond simply detecting if a species count becomes zero. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15584 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polynomial Equivalence of Extended Chemical Reaction Models Bajaj, Divya Castellanos, Jose Luis Knobel, Ryan Luchsinger, Austin Massie, Aiden Salinas, Adrian Santos, Pablo Santos, Ramiro Schweller, Robert Wylie, Tim Molecular Networks Computational Complexity The ability to detect whether a species (or dimension) is zero in Chemical Reaction Networks (CRN), Vector Addition Systems, or Petri Nets is known to increase the power of these models -- making them capable of universal computation. While this ability may appear in many forms, such as extending the models to allow transitions to be inhibited, prioritized, or synchronized, we present an extension that directly performs this zero checking. We introduce a new void genesis CRN variant with a simple design that merely increments the count of a specific species when any other species' count goes to zero. As with previous extensions, we show that the model is Turing Universal. We then analyze several other studied CRN variants and show that they are all equivalent through a polynomial simulation with the void genesis model, which does not merely follow from Turing-universality. Thus, inhibitor species, reactions that occur at different rates, being allowed to run reactions in parallel, or even being allowed to continually add more volume to the CRN, does not add additional simulation power beyond simply detecting if a species count becomes zero. |
| title | Polynomial Equivalence of Extended Chemical Reaction Models |
| topic | Molecular Networks Computational Complexity |
| url | https://arxiv.org/abs/2509.15584 |