Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Unique Assembly Verification in Two-Handed Self-Assembly

  • Published:
Algorithmica Aims and scope Submit manuscript

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 (\(\tau =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 (\(\tau = 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 \(\mathcal {O}(n^5)\) algorithm for UAV on tree-bonded assemblies when the temperature is fixed to 2, and a \(\mathcal {O}(n^5\log \tau )\) time algorithm when the temperature is part of the input.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

Notes

  1. While a formula may have multiple clauses without a parent, the authors of [26] show that by adding additional variables, an instance may be constructed with only a single root clause. For MP-3SAT-NVP, we need at least two clauses (one for the positive and negative sides).

  2. Without these base dominoes, variable gadgets could build without the full Bump due to backfilling or backwards growth. The dominoes ensure this can not happen.

  3. Having complimentary bump positions is equivalent to both representing the same assignment.

References

  1. Winfree, E.: Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology (1998)

  2. Meunier, P.-E., Regnault, D., Woods, D.: The program-size complexity of self-assembled paths. In: STOC: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2020, pp. 727–737. Association for Computing Machinery (2020). https://doi.org/10.1145/3357713.3384263

  3. Meunier, P.-E., Woods, D.: The non-cooperative tile assembly model is not intrinsically universal or capable of bounded turing machine simulation. In: STOC: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2017, pp. 328–341. Association for Computing Machinery (2017). https://doi.org/10.1145/3055399.3055446

  4. Cannon, S., Demaine, E.D., Demaine, M.L., Eisenstat, S., Patitz, M.J., Schweller, R.T., Summers, S.M., Winslow, A.: Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM. In: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), vol. 20, pp. 172–184. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik(2013)

  5. Chalk, C., Fernandez, D., Huerta, A., Maldonado, M., Schweller, R., Sweet, L.: Strict self-assembly of fractals using multiple hands. Algorithmica (2014). https://doi.org/10.1007/s00453-015-0022-x

    Article  MATH  Google Scholar 

  6. Hendricks, J., Opseth, J.: Self-assembly of 4-sided fractals in the two-handed tile assembly model. Nat. Comput. 18, 75–92 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cannon, S., Demaine, E.D., Demaine, M.L., Eisenstat, S., Furcy, D., Patitz, M.J., Schweller, R., Summers, S.M., Winslow, A.: On the effects of hierarchical self-assembly for reducing program-size complexity. Theoret. Comput. Sci. 894, 50–78 (2021). https://doi.org/10.1016/j.tcs.2021.09.011

    Article  MathSciNet  MATH  Google Scholar 

  8. Chen, H.-L., Doty, D.: Parallelism and time in hierarchical self-assembly. SIAM J. Comput. 46(2), 661–709 (2017)

  9. Adleman, L.M., Cheng, Q., Goel, A., Huang, M.-D.A., Kempe, D., de Espanés, P.M., Rothemund, P.W.K.: Combinatorial optimization problems in self-assembly. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 23–32 (2002)

  10. Winfree, E., Schulman, R., Evans, C.: The Xgrow Simulator. https://www.dna.caltech.edu/Xgrow/

  11. Patitz, M.: PyTAS. http://self-assembly.net/wiki/index.php?title=PyTAS

  12. Group, A.S.-A.R.: VersaTile. https://github.com/asarg/VersaTile (2014)

  13. Demaine, E.D., Demaine, M.L., Fekete, S.P., Ishaque, M., Rafalin, E., Schweller, R.T., Souvaine, D.L.: Staged self-assembly: nanomanufacture of arbitrary shapes with o(1) glues. Nat. Comput. 7(3), 347–370 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Aggarwal, G., Cheng, Q., Goldwasser, M.H., Kao, M.-Y., de Espanes, P.M., Schweller, R.T.: Complexities for generalized models of self-assembly. SIAM J. Comput. 34(6), 1493–1515 (2005). https://doi.org/10.1137/S0097539704445202

    Article  MathSciNet  MATH  Google Scholar 

  15. Patitz, M.J.: An introduction to tile-based self-assembly and a survey of recent results. Nat. Comput. 13(2), 195–224 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  16. Woods, D.: Intrinsic universality and the computational power of self-assembly. Philos. Trans. R. Soc. A Math. Phys. Eng. Sci. 373(2046), 20140214 (2015)

    Article  Google Scholar 

  17. Doty, D.: Theory of algorithmic self-assembly. Commun. ACM 55(12), 78–88 (2012)

    Article  Google Scholar 

  18. Woods, D., Doty, D., Myhrvold, C., Hui, J., Zhou, F., Yin, P., Winfree, E.: Diverse and robust molecular algorithms using reprogrammable DNA self-assembly. Nature 567(7748), 366–372 (2019). https://doi.org/10.1038/s41586-019-1014-9

    Article  Google Scholar 

  19. Doty, D.: Producibility in hierarchical self-assembly. In: Ibarra, O.H., Kari, L., Kopecki, S. (eds.) Unconventional Computation and Natural Computation, pp. 142–154. Springer, Cham (2014)

    Chapter  Google Scholar 

  20. Schweller, R., Winslow, A., Wylie, T.: Complexities for high-temperature two-handed tile self-assembly. In: Brijder, R., Qian, L. (eds.) DNA Computing and Molecular Programming, pp. 98–109. Springer (2017)

  21. Caballero, D., Gomez, T., Schweller, R., Wylie, T.: Complexity of verification in self-assembly with prebuilt assemblies. In: Proceedings of the Symposium on Algorithmic Foundations of Dynamic Networks. SAND’22, vol. 221, pp. 8–1815 (2022)

  22. Cantu, A.A., Luchsinger, A., Schweller, R., Wylie, T.: Covert Computation in self-assembled circuits. Algorithmica 83, 531–552 (2021). https://doi.org/10.1007/s00453-020-00764-w

    Article  MathSciNet  MATH  Google Scholar 

  23. Caballero, D., Gomez, T., Schweller, R., Wylie, T.: The complexity of multiple handed self-assembly. In: Kostitsyna, I., Orponen, P. (eds.) Unconventional Computation and Natural Computation, pp. 1–18. Springer, Cham (2021)

    Google Scholar 

  24. Schweller, R., Winslow, A., Wylie, T.: Verification in staged tile self-assembly. Nat. Comput. 18(1), 107–117 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  25. Caballero, D., Gomez, T., Schweller, R., Wylie, T.: Covert computation in staged self-assembly: Verification is pspace-complete. In: Proceedings of the 29th European Symposium on Algorithms. ESA’21, pp. 23–12318 (2021)

  26. Agarwal, P.K., Aronov, B., Geft, T., Halperin, D.: On two-handed planar assembly partitioning with connectivity constraints. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10–13, 2021, pp. 1740–1756. SIAM (2021). https://doi.org/10.1137/1.9781611976465.105

  27. Caballero, D., Gomez, T., Schweller, R., Wylie, T.: Unique assembly verification in two-handed self-assembly. In: Bojańczyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). ICALP’22, vol. 229, pp. 34–13421. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2022). https://doi.org/10.4230/LIPIcs.ICALP.2022.34.https://drops.dagstuhl.de/opus/volltexte/2022/16375

  28. Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422–427 (1992). https://doi.org/10.1137/0405033

    Article  MathSciNet  MATH  Google Scholar 

  29. Rothemund, P.W., Winfree, E.: The program-size complexity of self-assembled squares. In: Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, pp. 459–468 (2000)

  30. Schmidt, A., Manzoor, S., Huang, L., Becker, A., Fekete, S.P.: Efficient parallel self-assembly under uniform control inputs. Robot. Autom. Lett. 3, 3521–3528 (2018)

    Article  Google Scholar 

  31. Demaine, E.D., Fekete, S.P., Scheffer, C., Schmidt, A.: New geometric algorithms for fully connected staged self-assembly. Theoret. Comput. Sci. 671, 4–18 (2017)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

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

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Texas Rio Grande Valley, 1201 W. University Dr., Edinburg, TX, 78539-2999, USA

    David Caballero, Timothy Gomez, Robert Schweller & Tim Wylie

  2. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA, 02139, USA

    Timothy Gomez

Authors
  1. David Caballero
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Timothy Gomez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Robert Schweller
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tim Wylie
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tim Wylie.

Ethics declarations

Conflict of interest

To the best of our knowledge, we have no conflicts of interest related to the research. For publishing, Robert Schweller currently serves as an editor for the Algorithmica journal. For funding, Robert Schweller and Tim Wylie are PIs and received funding from the National Science Foundation (Grant CCF-1817602).

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Caballero, D., Gomez, T., Schweller, R. et al. Unique Assembly Verification in Two-Handed Self-Assembly. Algorithmica 85, 2427–2453 (2023). https://doi.org/10.1007/s00453-023-01103-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-023-01103-5

Keywords

Search

Navigation