Unique Assembly Verification in Two-Handed Self-Assembly
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 Asse...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151765 |
| _version_ | 1811093679376433152 |
|---|---|
| author | Caballero, David Gomez, Timothy Schweller, Robert Wylie, Tim |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Caballero, David Gomez, Timothy Schweller, Robert Wylie, Tim |
| author_sort | Caballero, David |
| collection | MIT |
| description | 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$$
τ
=
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$$
τ
=
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)$$
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 )$$
O
(
n
5
log
τ
)
time algorithm when the temperature is part of the input. |
| first_indexed | 2024-09-23T15:48:56Z |
| format | Article |
| id | mit-1721.1/151765 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:48:56Z |
| publishDate | 2023 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1517652024-02-17T04:23:29Z Unique Assembly Verification in Two-Handed Self-Assembly Caballero, David Gomez, Timothy Schweller, Robert Wylie, Tim Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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$$ τ = 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$$ τ = 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)$$ 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 )$$ O ( n 5 log τ ) time algorithm when the temperature is part of the input. 2023-08-16T20:29:21Z 2023-08-16T20:29:21Z 2023-02-17 2023-08-08T03:17:55Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/151765 Caballero, David, Gomez, Timothy, Schweller, Robert and Wylie, Tim. 2023. "Unique Assembly Verification in Two-Handed Self-Assembly." en https://doi.org/10.1007/s00453-023-01103-5 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature application/pdf Springer US Springer US |
| spellingShingle | Caballero, David Gomez, Timothy Schweller, Robert Wylie, Tim Unique Assembly Verification in Two-Handed Self-Assembly |
| title | Unique Assembly Verification in Two-Handed Self-Assembly |
| title_full | Unique Assembly Verification in Two-Handed Self-Assembly |
| title_fullStr | Unique Assembly Verification in Two-Handed Self-Assembly |
| title_full_unstemmed | Unique Assembly Verification in Two-Handed Self-Assembly |
| title_short | Unique Assembly Verification in Two-Handed Self-Assembly |
| title_sort | unique assembly verification in two handed self assembly |
| url | https://hdl.handle.net/1721.1/151765 |
| work_keys_str_mv | AT caballerodavid uniqueassemblyverificationintwohandedselfassembly AT gomeztimothy uniqueassemblyverificationintwohandedselfassembly AT schwellerrobert uniqueassemblyverificationintwohandedselfassembly AT wylietim uniqueassemblyverificationintwohandedselfassembly |