Difference between revisions of "Verification of 2HAM Systems"

From self-assembly wiki
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 4: Line 4:
  
 
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 <ref name=Versus /> 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.)
 
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 <ref name=Versus /> 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 <ref name=AGKS05g />
 
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 <ref name=AGKS05g />
 +
 
3) Is a given assembly terminal in 2HAM system $\mathcal{T}$?  In <ref name=Versus /> this was shown to be uncomputable for temperature 2 systems in the 2HAM (while it is computable in polynomial time in the aTAM <ref name=ACGHKMR02 />,  and also for the 2HAM at temperature 1 <ref name=Versus />.)
 
3) Is a given assembly terminal in 2HAM system $\mathcal{T}$?  In <ref name=Versus /> this was shown to be uncomputable for temperature 2 systems in the 2HAM (while it is computable in polynomial time in the aTAM <ref name=ACGHKMR02 />,  and also for the 2HAM at temperature 1 <ref name=Versus />.)
 +
 
4) Given a 2HAM system $\mathcal{T}$, does it produce a finite terminal assembly?  This was shown to be uncomputable in <ref name=Versus />.
 
4) Given a 2HAM system $\mathcal{T}$, does it produce a finite terminal assembly?  This was shown to be uncomputable in <ref name=Versus />.
 +
 
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 <ref name=Versus />.
 
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 <ref name=Versus />.
  
Line 47: Line 51:
  
 
[[Category: 2HAM Results]]
 
[[Category: 2HAM Results]]
 +
[[Category:Self-assembly]]

Latest revision as of 14:03, 27 May 2014

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 [1] 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 [2]

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

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

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 [1].


References

  1. ↑ 1.0 1.1 1.2 1.3 1.4 Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow - Two Hands Are Better Than One (up to constant factors)
    Technical Report, Computing Research Repository (1201.1650),2012
    http://arxiv.org/abs/1201.1650
    Bibtex
    Author : Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow
    Title : Two Hands Are Better Than One (up to constant factors)
    In : Technical Report, Computing Research Repository -
    Address :
    Date : 2012
  2. ↑ Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, Pablo Moisset de Espan\'es - Complexities for Generalized Models of Self-Assembly
    SIAM Journal on Computing 34:1493--1515,2005
    Bibtex
    Author : Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, Pablo Moisset de Espan\'es
    Title : Complexities for Generalized Models of Self-Assembly
    In : SIAM Journal on Computing -
    Address :
    Date : 2005
  3. ↑ Cite error: Invalid <ref> tag; no text was provided for refs named ACGHKMR02
Retrieved from "http://self-assembly.net/wiki/index.php?title=Verification_of_2HAM_Systems&oldid=1178"