Verification of aTAM systems

From self-assembly wiki
Revision as of 20:21, 10 July 2013 by \('"2\)'"7
(\(1) \)2 | \(3 (\)4) | \(5 (\)6)
Jump to navigation Jump to search

Several "verification problems" (answering the question of whether or not a given system has a specific property) have been studied in relation to the aTAM, and characterized by their complexity. Among them are:

\begin{enumerate} \item Does aTAM system '"`UNIQ-MathJax2-QINU`"' uniquely produce a given assembly? This was shown to require time polynomial in the size of the assembly and tile set by Adleman, et al. in \cite{ACGHKMR02}. \item Does aTAM system '"`UNIQ-MathJax3-QINU`"' uniquely produce a given shape? This was shown to be in co-NP-complete for temperature 1 by Cannon, et al. in \cite{Versus} and co-NP-complete for temperature 2 in \cite{AGKS05g} by Cheng, et al. \item Is a given assembly terminal in aTAM system '"`UNIQ-MathJax4-QINU`"'? This was shown to require time linear in the size of the assembly and tile set in \cite{ACGHKMR02} \item Given an aTAM system '"`UNIQ-MathJax5-QINU`"', does it produce a finite terminal assembly? An infinite terminal assembly? These were both shown to be uncomputable in \cite{Versus}. \end{enumerate}

References

Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.
Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.
Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.
Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.
Cite error: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.