LIPIcs.SAND.2022.24.pdf
- Filesize: 0.51 MB
- 3 pages
Document
Brief Announcement: Barrier-1 Reachability for Thermodynamic Binding Networks Is PSPACE-Complete
Author
-
Part of:
Volume:
1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Algorithmic Foundations of Dynamic Networks (SAND) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-04-29
File
Document Identifiers
Acknowledgements
The author would like to thank the reviewers for their detailed reading and constructive feedback.
Cite As Get BibTex
Austin Luchsinger. Brief Announcement: Barrier-1 Reachability for Thermodynamic Binding Networks Is PSPACE-Complete. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 24:1-24:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.24
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).
Subject Classification
ACM Subject Classification
- Theory of computation → Models of computation
Keywords
- Thermodynamic Binding Networks
- Nondeterministic Constraint Logic
- NP-complete
- PSPACE-complete
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Aaron Becker, Erik D. Demaine, Sándor P. Fekete, Golnaz Habibi, and James McLurkin. Reconfiguring massive particle swarms with limited, global control. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pages 51-66. Springer, 2013.
-
Keenan Breik, Cameron Chalk, David Haley, David Doty, and David Soloveichik. Programming substrate-independent kinetic barriers with thermodynamic binding networks. IEEE/ACM transactions on computational biology and bioinformatics, 2019.
-
Keenan Breik, Chris Thachuk, Marijn Heule, and David Soloveichik. Computing properties of stable configurations of thermodynamic binding networks. Theoretical Computer Science, 785:17-29, 2019.
-
Boris De Wilde, Adriaan W. Ter Mors, and Cees Witteveen. Push and rotate: a complete multi-agent pathfinding algorithm. Journal of Artificial Intelligence Research, 51:443-492, 2014.
-
David Doty, Trent A. Rogers, David Soloveichik, Chris Thachuk, and Damien Woods. Thermodynamic binding networks. In Robert Brijder and Lulu Qian, editors, DNA Computing and Molecular Programming, pages 249-266, Cham, 2017. Springer International Publishing.
- David Haley and David Doty. Computing properties of thermodynamic binding networks: An integer programming approach. arXiv preprint, 2020. URL: http://arxiv.org/abs/2011.10677.
-
Robert A. Hearn and Erik D. Demaine. Games, puzzles, and computation. CRC Press, 2009.
-
Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, 1970.
-
Kiril Solovey and Dan Halperin. On the hardness of unlabeled multi-robot motion planning. The International Journal of Robotics Research, 35(14):1750-1759, 2016.