Paper by Erik D. Demaine
- Robert M. Alaniz, Josh Brunner, Michael Coulombe, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Elise Grizzell, Ryan Knobel, Jayson Lynch, Andrew Rodriguez, Robert Schweller, and Tim Wylie, “Complexity of Reconfiguration in Surface Chemical Reaction Networks”, in Proceedings of the 29th International Conference on DNA Computing and Molecular Programming (DNA 2019), LIPIcs, September 11–15, 2023, 10:1–10:18.
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).
- This paper is also available from LIPIcs and as arXiv:2303.15556.
- The paper is 18 pages.
- The paper is available in PDF (786k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by