2026-07-23T08:16:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18793 2024-03-06T11:02:53Z ddc:004 open_access

Complexity of Reconfiguration in Surface Chemical Reaction Networks Alaniz, Robert M. Brunner, Josh Coulombe, Michael Demaine, Erik D. Diomidova, Jenny Gomez, Timothy Grizzell, Elise Knobel, Ryan Lynch, Jayson Rodriguez, Andrew Schweller, Robert Wylie, Tim Chemical Reaction Networks reconfiguration hardness We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent species nondeterministically transform into a different ordered pair of species according to a predefined set of allowed transition rules (chemical reactions). In particular, two questions that are fundamental to the simulation of sCRNs are whether a given configuration of molecules can ever transform into another given configuration, and whether a given cell can ever contain a given species, given a set of transition rules. We show that these problems can be solved in polynomial time, are NP-complete, or are PSPACE-complete in a variety of different settings, including when adjacent species just swap instead of arbitrary transformation (swap sCRNs), and when cells can change species a limited number of times (k-burnout). Most problems turn out to be at least NP-hard except with very few distinct species (2 or 3). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert M. Alaniz and Josh Brunner and Michael Coulombe and Erik D. Demaine and Jenny Diomidova and Timothy Gomez and Elise Grizzell and Ryan Knobel and Jayson Lynch and Andrew Rodriguez and Robert Schweller and Tim Wylie 2023 Is Part Of LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DNA.29.10 urn:nbn:de:0030-drops-187936 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.10 eng https://creativecommons.org/licenses/by/4.0/legalcode