Verification of 2HAM Systems

Given that the 2HAM allows for a greater variety of behaviors than the aTAM, and in fact in some sense for the transmission of information over arbitrary distances (by the placements of glues and general geometric shapes of arbitrarily large supertiles which are combining), it shouldn't be surprising that many verification problems are more difficult for the 2HAM than for the aTAM (see Verification of aTAM systems).

Several verification problems have been characterized in terms of their complexity, some of which include:

1) Does 2HAM system \(\mathcal[T]\) uniquely produce a given assembly? This was shown to be co-NP-complete for 3D temperature 2 systems in the 2HAM in by Cannon, et al. The complexity of this verification problem is still open in 2D. (But note that it is solvable in polynomial time in the aTAM in both 2D and 3D.)

2) Does 2HAM system \(\mathcal{T}\) uniquely produce a given shape? This was shown to be in co-NP for temperature 1 and co-NP-complete for temperature 2 by Cheng, et al. in

3) Is a given assembly terminal in 2HAM system \(\mathcal{T}\)? In this was shown to be uncomputable for temperature 2 systems in the 2HAM (while it is computable in polynomial time in the aTAM , and also for the 2HAM at temperature 1 .)

4) Given a 2HAM system \(\mathcal{T}\), does it produce a finite terminal assembly? This was shown to be uncomputable in .

5)Given a 2HAM system \(\mathcal{T}\), does it produce an infinite terminal assembly? This was shown to be uncomputable for temperature 2 2HAM systems in .