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