April 8, 2022

About the speaker

Mr. David Caballero is a graduate student from the Computer Science department.

Complexity of Verification in Self-Assembly with Prebuilt Assemblies

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 O(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.