Verification in Staged Tile Self-Assembly

Abstract

We prove the unique assembly and unique shape verification problems, benchmark measures of self-assembly model power, are ${\mathrm{coNP}}^{\mathrm{NP}}$-hard and contained in $\mathrm{PSPACE}$ (and in ${\mathrm{\Pi }}_{2s}^{\mathrm{P}}$ for staged systems with $s$ stages). En route, we prove that unique shape verification problem in the 2HAM is ${\mathrm{coNP}}^{\mathrm{NP}}$-complete.

An abstract version will appear in the proceedings of UCNC 2017