  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$). 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$), 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)$ algorithm for UAV on
tree-bonded assemblies when the temperature is fixed to $2$, and a
$\mathcal{O}(n^5\log \tau)$ time algorithm when the temperature is part of the
input.
