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.SAND.2022.24
URN: urn:nbn:de:0030-drops-159664
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15966/
Go to the corresponding LIPIcs Volume Portal

Luchsinger, Austin

Brief Announcement: Barrier-1 Reachability for Thermodynamic Binding Networks Is PSPACE-Complete

pdf-format:
LIPIcs-SAND-2022-24.pdf (0.5 MB)

Abstract

Chemical and molecular systems exist in a world between kinetics and thermodynamics. Engineers of such systems often design them to perform computation solely by following particular kinetic pathways. That is, just like silicon computation, these systems are intentionally designed to run contrary to the natural thermodynamic driving forces of the system. The thermodynamic binding networks (TBN) model is a relatively new model that is particularly well-equipped to investigate this dichotomy between kinetics and thermodynamics. The kinetic TBN model uses reconfiguration energy barriers to inform kinetic pathways. This work shows that deciding if two TBN configurations have a barrier-1 pathway between them is PSPACE-complete. This result comes via a reduction from nondeterministic constraint logic (NCL).

BibTeX - Entry

@InProceedings{luchsinger:LIPIcs.SAND.2022.24,
  author =	{Luchsinger, Austin},
  title =	{{Brief Announcement: Barrier-1 Reachability for Thermodynamic Binding Networks Is PSPACE-Complete}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{24:1--24:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15966},
  URN =		{urn:nbn:de:0030-drops-159664},
  doi =		{10.4230/LIPIcs.SAND.2022.24},
  annote =	{Keywords: Thermodynamic Binding Networks, Nondeterministic Constraint Logic, NP-complete, PSPACE-complete}
}

Keywords: Thermodynamic Binding Networks, Nondeterministic Constraint Logic, NP-complete, PSPACE-complete
Collection: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Issue Date: 2022
Date of publication: 29.04.2022

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