EUVIMEDEUVIMED entdecken
Crossref

Reachability in Deletion-Only Chemical Reaction Networks

Fu, Bin, Timothy Gomez, Ryan Knobel, Austin Luchsinger, Aiden Massie, Rodriguez, Marco, Adrian Salinas, Robert Schweller, Wylie, Tim

DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 01.01.2025

DOI: 10.4230/lipics.dna.31.3 ↗

Kurz gefasst

Fachartikel in der Zeitschrift DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), erschienen am 01.01.2025. Verfasst von Fu und 11 weiteren Autor:innen.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For general discrete Chemical Reaction Networks (CRNs), the fundamental problem of reachability - the question of whether a target configuration can be produced from a given initial configuration - was recently shown to be Ackermann-complete. However, many open questions remain about which features of the CRN model drive this complexity. We study a restricted class of CRNs with void rules, reactions that only decrease species counts. We further examine this regime in the motivated model of step CRNs, which allow additional species to be introduced in discrete stages. With and without steps, we characterize the complexity of the reachability problem for CRNs with void rules. We show that, without steps, reachability remains polynomial-time solvable for bimolecular systems but becomes NP-complete for larger reactions. Conversely, with just a single step, reachability becomes NP-complete even for bimolecular systems. Our results provide a nearly complete classification of void-rule reachability problems into tractable and intractable cases, with only a single exception.

Schlagwörter

chemical reaction networksreachability problemNP-completenesscomputational complexitybimolecular reactions

Zitieren

APA

Fu, Bin, Gomez, T., Knobel, R., Luchsinger, A., Massie, A., Rodriguez, Marco, Salinas, A., Schweller, R., Wylie, & Tim (2025). Reachability in Deletion-Only Chemical Reaction Networks. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). https://doi.org/10.4230/lipics.dna.31.3

Vancouver

Fu, Bin, Gomez T, Knobel R, Luchsinger A, Massie A, et al. Reachability in Deletion-Only Chemical Reaction Networks. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). 2025. doi:10.4230/lipics.dna.31.3

BibTeX
@article{Fu2025,
  author = {Fu and Bin and Gomez, Timothy and Knobel, Ryan and Luchsinger, Austin and Massie, Aiden and Rodriguez and Marco and Salinas, Adrian and Schweller, Robert and Wylie and Tim},
  title = {Reachability in Deletion-Only Chemical Reaction Networks},
  journal = {DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)},
  year = {2025},
  doi = {10.4230/lipics.dna.31.3}
}
Kostenlos starten →