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

Author Austin Luchsinger



PDF
Thumbnail PDF

File

LIPIcs.SAND.2022.24.pdf
  • Filesize: 0.51 MB
  • 3 pages

Document Identifiers

Author Details

Austin Luchsinger
  • The University of Texas at Austin, TX, USA

Acknowledgements

The author would like to thank the reviewers for their detailed reading and constructive feedback.

Cite AsGet 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)
    0
    PDF Downloads

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. 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. Google Scholar
  5. 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. Google Scholar
  6. 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.
  7. Robert A. Hearn and Erik D. Demaine. Games, puzzles, and computation. CRC Press, 2009. Google Scholar
  8. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, 1970. Google Scholar
  9. 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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail