Document Open Access Logo

Unique Assembly Verification in Two-Handed Self-Assembly

Authors David Caballero, Timothy Gomez, Robert Schweller, Tim Wylie

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.34.pdf
  • Filesize: 1.19 MB
  • 21 pages

Document Identifiers

Author Details

David Caballero
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Timothy Gomez
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Robert Schweller
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA
Tim Wylie
  • Department of Computer Science, University of Texas Rio Grande Valley, TX, USA

Funding

This research was supported in part by National Science Foundation Grant CCF-1817602.

Cite As Get BibTex

David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie. Unique Assembly Verification in Two-Handed Self-Assembly. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.34

Abstract

One of the most fundamental and well-studied problems in tile self-assembly is the Unique Assembly Verification (UAV) problem. This algorithmic problem asks whether a given tile system uniquely assembles a specific assembly. The complexity of this problem in the 2-Handed Assembly Model (2HAM) at a constant temperature is a long-standing open problem since the model was introduced. Previously, only membership in the class coNP was known and that the problem is in P if the temperature is one (τ = 1). The problem is known to be hard for many generalizations of the model, such as allowing one step into the third dimension or allowing the temperature of the system to be a variable, but the most fundamental version has remained open.
In this paper, we prove the UAV problem in the 2HAM is hard even with a small constant temperature (τ = 2), and finally answer the complexity of this problem (open since 2013). Further, this result proves that UAV in the staged self-assembly model is coNP-complete with a single bin and stage (open since 2007), and that UAV in the q-tile model is also coNP-complete (open since 2004). We reduce from Monotone Planar 3-SAT with Neighboring Variable Pairs, a special case of 3SAT recently proven to be NP-hard. We accompany this reduction with a positive result showing that UAV is solvable in polynomial time with the promise that the given target assembly will have a tree-shaped bond graph, i.e., contains no cycles. We provide a 𝒪(n⁵) algorithm for UAV on tree-bonded assemblies when the temperature is fixed to 2, and a 𝒪(n⁵log τ) time algorithm when the temperature is part of the input.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Applied computing → Computational biology
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Self-organization
Keywords
  • self-assembly
  • unique assembly verification
  • 2-handed assembly model

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Leonard Adleman, Qi Cheng, Ashish Goel, and Ming-Deh Huang. Running time and program size for self-assembled squares. In Proceedings of the 33rd ACM Symposium on Theory of Computing, STOC'01, pages 740-748, 2001. URL: https://doi.org/10.1145/380752.380881.
  2. Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, and Paul W. K. Rothemund. Combinatorial optimization problems in self-assembly. In Proc. of the 34th ACM Sym. on Theory of Computing, pages 23-32, 2002. Google Scholar
  3. Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, and Dan Halperin. On two-handed planar assembly partitioning with connectivity constraints. In Proc. of the ACM-SIAM Syme on Discrete Algorithms, SODA'21, pages 1740-1756, 2021. URL: https://doi.org/10.1137/1.9781611976465.105.
  4. Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset de Espanes, and Robert T. Schweller. Complexities for generalized models of self-assembly. SIAM Journal on Computing, 34(6):1493-1515, 2005. URL: https://doi.org/10.1137/S0097539704445202.
  5. David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie. The complexity of multiple handed self-assembly. In Proceedings of the International Conference on Unconventional Computation and Natural Computation, UCNC'21, pages 1-18, 2021. Google Scholar
  6. David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie. Covert computation in staged self-assembly: Verification is pspace-complete. In Proceedings of the 29th European Symposium on Algorithms, ESA'21, pages 23:1-23:18, 2021. Google Scholar
  7. David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie. Complexity of verification in self-assembly with prebuilt assemblies. In Proceedings of the Symposium on Algorithmic Foundations of Dynamic Networks, SAND'22, 2022. Google Scholar
  8. Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, David Furcy, Matthew J. Patitz, Robert Schweller, Scott M. Summers, and Andrew Winslow. On the effects of hierarchical self-assembly for reducing program-size complexity. Theoretical Computer Science, 894:50-78, 2021. URL: https://doi.org/10.1016/j.tcs.2021.09.011.
  9. Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M Summers, and Andrew Winslow. Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. In 30th Inter. Sym. on Theoretical Aspects of Computer Science, volume 20 of STACS'13, pages 172-184, 2013. Google Scholar
  10. Angel A. Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie. Covert Computation in Self-Assembled Circuits. Algorithmica, 83:531-552, 2021. arXiv:1908.06068. Google Scholar
  11. Cameron Chalk, Dominic Fernandez, Alejandro Huerta, Mario Maldonado, Robert Schweller, and Leslie Sweet. Strict self-assembly of fractals using multiple hands. Algorithmica, 76, July 2014. URL: https://doi.org/10.1007/s00453-015-0022-x.
  12. Ho-Lin Chen and David Doty. Parallelism and time in hierarchical self-assembly. SIAM Journal on Computing, 46(2):661-709, 2017. Preliminary version appeared in SODA 2012. Google Scholar
  13. Erik D Demaine, Martin L Demaine, Sándor P Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T Schweller, and Diane L Souvaine. Staged self-assembly: nanomanufacture of arbitrary shapes with o(1) glues. Natural Computing, 7(3):347-370, 2008. Google Scholar
  14. Erik D. Demaine, Sándor P. Fekete, Christian Scheffer, and Arne Schmidt. New geometric algorithms for fully connected staged self-assembly. Theoretical Comp. Science, 671:4-18, 2017. Google Scholar
  15. David Doty. Theory of algorithmic self-assembly. Comm. of the ACM, 55(12):78-88, 2012. Google Scholar
  16. David Doty. Producibility in hierarchical self-assembly. In Proc. of the Inter. Conf. on Unconventional Computation and Natural Computation, UCNC'14, pages 142-154, 2014. Google Scholar
  17. Algorithmic Self-Assembly Research Group. VersaTile. github.com/asarg/VersaTile, 2014. Google Scholar
  18. Jacob Hendricks and Joseph Opseth. Self-assembly of 4-sided fractals in the two-handed tile assembly model. Natural Computing, 18:75-92, 2018. Google Scholar
  19. Donald E. Knuth and Arvind Raghunathan. The problem of compatible representatives. SIAM Journal on Discrete Mathematics, 5(3):422-427, 1992. URL: https://doi.org/10.1137/0405033.
  20. Pierre-'Etienne Meunier, Damien Regnault, and Damien Woods. The program-size complexity of self-assembled paths. In Proc. of the 52nd Annual ACM SIGACT Sym. on Theory of Computing, STOC 2020, pages 727-737, 2020. URL: https://doi.org/10.1145/3357713.3384263.
  21. Pierre-'Etienne Meunier and Damien Woods. The non-cooperative tile assembly model is not intrinsically universal or capable of bounded turing machine simulation. In Proc. of the 49th Annual ACM SIGACT Sym. on Theory of Computing, STOC'17, pages 328-341, 2017. Google Scholar
  22. Matt Patitz. Pytas. URL: http://self-assembly.net/wiki/index.php?title=PyTAS.
  23. Matthew J. Patitz. An introduction to tile-based self-assembly and a survey of recent results. Natural Computing, 13(2):195-224, June 2014. Google Scholar
  24. Paul WK Rothemund and Erik Winfree. The program-size complexity of self-assembled squares. In Proc. of the 32nd annual ACM Sym. on Theory of computing, pages 459-468, 2000. Google Scholar
  25. Arne Schmidt, Sheryl Manzoor, Li Huang, Aaron Becker, and Sándor P. Fekete. Efficient parallel self-assembly under uniform control inputs. Robotics and Automation Letters, 3:3521-3528, 2018. Google Scholar
  26. Robert Schweller, Andrew Winslow, and Tim Wylie. Complexities for high-temperature two-handed tile self-assembly. In Proc. of the 23rd Inter. Conf. on DNA Computing and Molecular Programming, DNA'17, pages 98-109, 2017. Google Scholar
  27. Robert Schweller, Andrew Winslow, and Tim Wylie. Verification in staged tile self-assembly. Natural Computing, 18(1):107-117, 2019. Google Scholar
  28. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, June 1998. Google Scholar
  29. Erik Winfree, Rebecca Schulman, and Constantine Evans. The xgrow simulator. URL: https://www.dna.caltech.edu/Xgrow/.
  30. Damien Woods. Intrinsic universality and the computational power of self-assembly. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 373(2046):20140214, 2015. Google Scholar
  31. Damien Woods, David Doty, Cameron Myhrvold, Joy Hui, Felix Zhou, Peng Yin, and Erik Winfree. Diverse and robust molecular algorithms using reprogrammable dna self-assembly. Nature, 567(7748):366-372, 2019. URL: https://doi.org/10.1038/s41586-019-1014-9.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact