License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DNA.29.10
URN: urn:nbn:de:0030-drops-187936
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18793/
Go to the corresponding LIPIcs Volume Portal

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

Complexity of Reconfiguration in Surface Chemical Reaction Networks

pdf-format:
LIPIcs-DNA-29-10.pdf (0.8 MB)

Abstract

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).

BibTeX - Entry

@InProceedings{alaniz_et_al:LIPIcs.DNA.29.10,
  author =	{Alaniz, Robert M. and Brunner, Josh and Coulombe, Michael and Demaine, Erik D. and Diomidova, Jenny and Gomez, Timothy and Grizzell, Elise and Knobel, Ryan and Lynch, Jayson and Rodriguez, Andrew and Schweller, Robert and Wylie, Tim},
  title =	{{Complexity of Reconfiguration in Surface Chemical Reaction Networks}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18793},
  URN =		{urn:nbn:de:0030-drops-187936},
  doi =		{10.4230/LIPIcs.DNA.29.10},
  annote =	{Keywords: Chemical Reaction Networks, reconfiguration, hardness}
}

Keywords: Chemical Reaction Networks, reconfiguration, hardness
Collection: 29th International Conference on DNA Computing and Molecular Programming (DNA 29)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI