2026-07-21T23:20:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15950 2024-03-06T10:56:29Z ddc:004 open_access

Complexity of Verification in Self-Assembly with Prebuilt Assemblies Caballero, David Gomez, Timothy Schweller, Robert Wylie, Tim 2-handed assembly verification prebuilt We analyze the complexity of two fundamental verification problems within a generalization of the two-handed tile self-assembly model (2HAM) where initial system assemblies are not restricted to be singleton tiles, but may be larger pre-built assemblies. Within this model we consider the producibility problem, which asks if a given tile system builds, or produces, a given assembly, and the unique assembly verification (UAV) problem, which asks if a given system uniquely produces a given assembly. We show that producibility is NP-complete and UAV is coNP^{NP}-complete even when the initial assembly size and temperature threshold are both bounded by a constant. This is in stark contrast to results in the standard model with singleton input tiles where producibility is in P and UAV is in coNP for 𝒪(1) bounded temperature and coNP-complete when temperature is part of the input. We further provide preliminary results for producibility and UAV in the case of 1-dimensional linear assemblies with pre-built assemblies, and provide polynomial time solutions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Caballero and Timothy Gomez and Robert Schweller and Tim Wylie 2022 Is Part Of LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2022.8 urn:nbn:de:0030-drops-159503 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.8 eng https://creativecommons.org/licenses/by/4.0/legalcode