Difference between revisions of "Open Problems"
Jump to navigation
Jump to search
(Marked open problems which have been solved, with references) |
|||
| Line 4: | Line 4: | ||
<ul> | <ul> | ||
| − | <li>In his 1998 thesis <ref name=Winf98 />, Winfree showed that the class of directed [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems at temperature 2 is computationally universal, and in <ref name=CooFuSch11/> Cook et al. showed that undirected temperature 1 aTAM systems could perform computations with a given amount of certainty. They also showed that in 2 planes directed aTAM temperature 1 systems are computationally universal. Is the class of directed aTAM systems at temperature 1 in the plane computationally universal? In <ref name=jLSAT1 /> Doty, Patitz, and Summers provide insights into this question. | + | <li>In his 1998 thesis <ref name=Winf98 />, Winfree showed that the class of directed [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems at temperature 2 is computationally universal, and in <ref name=CooFuSch11/> Cook et al. showed that undirected temperature 1 aTAM systems could perform computations with a given amount of certainty. They also showed that in 2 planes directed aTAM temperature 1 systems are computationally universal. Is the class of directed aTAM systems at temperature 1 in the plane computationally universal? In <ref name=jLSAT1 /> Doty, Patitz, and Summers provide insights into this question. </li> |
| + | |||
| + | SOLVED<ref name=TEMP1NONTURING /><ref name=TEMP1NONUNIVERSAL /> | ||
| + | |||
| + | <li> Can $n \times n$ squares efficiently self-assemble at temperature 1 (i.e. can less than $O(n)$ tile types be used)? </li> | ||
<li>In <ref name = SFTSAFT/>, Doty et al. introduced a model known as the [[Fuzzy Temperature Fault Tolerance | fuzzy temperature model]] and showed that in this model n by n squares could efficiently self-assemble. Can systems in this model also perform general computation?</li> | <li>In <ref name = SFTSAFT/>, Doty et al. introduced a model known as the [[Fuzzy Temperature Fault Tolerance | fuzzy temperature model]] and showed that in this model n by n squares could efficiently self-assemble. Can systems in this model also perform general computation?</li> | ||
<li>In [[Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue]], Patitz et al. introduced the ``restricted glue TAM`` (rgTAM), a version of the aTAM in which a single glue whose strength is -1 (i.e. it is repulsive) is allowed, and all other glues must be strength 1. They showed that it is computationally universal. However, is a 2HAM version of the rgTAM also computationally universal?</li> | <li>In [[Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue]], Patitz et al. introduced the ``restricted glue TAM`` (rgTAM), a version of the aTAM in which a single glue whose strength is -1 (i.e. it is repulsive) is allowed, and all other glues must be strength 1. They showed that it is computationally universal. However, is a 2HAM version of the rgTAM also computationally universal?</li> | ||
| + | |||
| + | SOLVED<ref name=rg2HAM /> | ||
| + | |||
| + | |||
<li>In <ref name = IUSA /> Doty et al. showed that the aTAM is [[Intrinsic universality of the aTAM | intrinsically universal]] for itself, but for [[Directed Tile Assembly Systems | directed]] systems the intrinsically universal tile set fundamentally relies on nondeterminism. Is the class of directed [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems intrinsically universal for itself?</li> | <li>In <ref name = IUSA /> Doty et al. showed that the aTAM is [[Intrinsic universality of the aTAM | intrinsically universal]] for itself, but for [[Directed Tile Assembly Systems | directed]] systems the intrinsically universal tile set fundamentally relies on nondeterminism. Is the class of directed [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems intrinsically universal for itself?</li> | ||
| + | |||
| + | SOLVED<ref name=DirectedIU /> | ||
<li>Is the [[STAM]] [[Intrinsic Universality in the 2HAM | intrinsically universal]] for itself? Also, in <ref name=STAMIU /> it was shown that the 3D aTAM is IU for a subset of the STAM, but it remains open whether or not adding negative strength glues allows the 3D aTAM to be IU for the full STAM. Additionally related to the STAM, for every Staged Assembly Model system is there an STAM system which can simulate it?</li> | <li>Is the [[STAM]] [[Intrinsic Universality in the 2HAM | intrinsically universal]] for itself? Also, in <ref name=STAMIU /> it was shown that the 3D aTAM is IU for a subset of the STAM, but it remains open whether or not adding negative strength glues allows the 3D aTAM to be IU for the full STAM. Additionally related to the STAM, for every Staged Assembly Model system is there an STAM system which can simulate it?</li> | ||
<li>Is the class of [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems at temperature 1 [[Intrinsic universality of the aTAM | intrinsically universal]] for itself?</li> | <li>Is the class of [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems at temperature 1 [[Intrinsic universality of the aTAM | intrinsically universal]] for itself?</li> | ||
| + | |||
| + | SOLVED<ref name=TEMP1NONUNIVERSAL /> | ||
<li>In his 1998 thesis <ref name=Winf98 />, Winfree introduced both the [[Abstract Tile Assembly Model (aTAM) | aTAM]] and its more practical counterpart the [[Kinetic Tile Assembly Model (kTAM) | kTAM]]. Currently, the 2HAM does not have a more realistic counterpart. Formulate a "k2HAM" model which takes into account the size of assemblies binding together (the bigger the assemblies the less likely it is they will bind together) and the lack of rigidity when assemblies come together.</li> | <li>In his 1998 thesis <ref name=Winf98 />, Winfree introduced both the [[Abstract Tile Assembly Model (aTAM) | aTAM]] and its more practical counterpart the [[Kinetic Tile Assembly Model (kTAM) | kTAM]]. Currently, the 2HAM does not have a more realistic counterpart. Formulate a "k2HAM" model which takes into account the size of assemblies binding together (the bigger the assemblies the less likely it is they will bind together) and the lack of rigidity when assemblies come together.</li> | ||
<li>In [[Self-Assembly of Discrete Self-Similar Fractals]], Patitz and Summers proved several results about self-assembling discrete self-similar fractals, but it is still an open questions as to whether or not there exists a discrete self-similar fractal that can be self-assembled in the [[Abstract Tile Assembly Model (aTAM) | aTAM]]. Also, are there discrete self-similar fractals which are not pinch-point fractals that are provably impossible to strictly self-assemble (e.g. the Sierpinski carpet)?</li> | <li>In [[Self-Assembly of Discrete Self-Similar Fractals]], Patitz and Summers proved several results about self-assembling discrete self-similar fractals, but it is still an open questions as to whether or not there exists a discrete self-similar fractal that can be self-assembled in the [[Abstract Tile Assembly Model (aTAM) | aTAM]]. Also, are there discrete self-similar fractals which are not pinch-point fractals that are provably impossible to strictly self-assemble (e.g. the Sierpinski carpet)?</li> | ||
| + | |||
| + | SOLVED <ref name=DSSFQuines /> <ref name=DSSFSDC /> | ||
<li>In [[Self-Assembly with Geometric Tiles]], a construction was shown in which 2D tiles with disconnected geometries which are forced to stay within the plane as they combine, are capable of assembling n by n squares using only $O(\log(\log(n)))$ tile types. Can a similar construction be shown with connected geometries (and staying in 2D)?</li> | <li>In [[Self-Assembly with Geometric Tiles]], a construction was shown in which 2D tiles with disconnected geometries which are forced to stay within the plane as they combine, are capable of assembling n by n squares using only $O(\log(\log(n)))$ tile types. Can a similar construction be shown with connected geometries (and staying in 2D)?</li> | ||
| Line 27: | Line 41: | ||
<li>In [[Two Hands Are Better Than One (up to constant factors)]], among other results, Cannon et al. proved that in the 3D 2HAM, if you are given a system $\mathcal{T}$ and an assembly $\alpha$, it is co-NP complete to determine if $\alpha$ is the unique terminal assembly of $\mathcal{T}$. It remains open what the complexity of this problem is in 2D. In the same paper, they showed how any aTAM system can be simulated by a 2HAM system at scale factor 5. It remains open how small this scale factor can actually be.</li> | <li>In [[Two Hands Are Better Than One (up to constant factors)]], among other results, Cannon et al. proved that in the 3D 2HAM, if you are given a system $\mathcal{T}$ and an assembly $\alpha$, it is co-NP complete to determine if $\alpha$ is the unique terminal assembly of $\mathcal{T}$. It remains open what the complexity of this problem is in 2D. In the same paper, they showed how any aTAM system can be simulated by a 2HAM system at scale factor 5. It remains open how small this scale factor can actually be.</li> | ||
| + | |||
| + | SOLVED<ref name=UAV2HAM /> | ||
==References== | ==References== | ||
| Line 107: | Line 123: | ||
</bibtex></ref> | </bibtex></ref> | ||
| + | <ref name=TEMP1NONUNIVERSAL><bibtex> | ||
| + | @inproceedings{STOC, | ||
| + | author = {Pierre-Étienne Meunier and | ||
| + | Damien Woods}, | ||
| + | title = {The non-cooperative tile assembly model is not intrinsically | ||
| + | universal or capable of bounded Turing machine simulation} | ||
| + | booktitlev= {STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium | ||
| + | on Theory of Computing}, | ||
| + | year = {2017}, | ||
| + | pages = {328-341} | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | |||
| + | <ref name=rg2HAM><bibtex> | ||
| + | @inproceedings{DNA, | ||
| + | author = {Matthew J. Patitz and | ||
| + | Trent A. Rogers and | ||
| + | Robert T. Schweller and | ||
| + | Scott M. Summers and | ||
| + | Andrew Winslow}, | ||
| + | title = {Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly} | ||
| + | booktitlev= {DNA Computing and Molecular Programming - 22nd International | ||
| + | Conference, DNA 22, Munich, Germany, September 4-28, 201^. | ||
| + | Proceedings}, | ||
| + | year = {2016}, | ||
| + | pages = {98-113} | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | |||
| + | <ref name=DirectedIU><bibtex> | ||
| + | @inproceedings{SODA, | ||
| + | author = {Pierre-Étienne Meunier and | ||
| + | Matthew J. Patitz and | ||
| + | Scott M. Summers and | ||
| + | Guillaume Theyssier and | ||
| + | Andrew Winslow and | ||
| + | Damien Woods}, | ||
| + | title = {Intrinsic universality in tile self-assembly requires cooperation} | ||
| + | booktitlev= {SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete | ||
| + | Algorithms}, | ||
| + | year = {2014}, | ||
| + | pages = {752-771} | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | |||
| + | <ref name=DSSFQuines><bibtex> | ||
| + | @unpublished{ | ||
| + | author = {Daniel Hader and | ||
| + | Matthew J. Patitz}, | ||
| + | title = {Strictly Self-Assembling Discrete Self-Similar Fractals Using Quines} | ||
| + | year = {2024}, | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | <ref name=DSSFSDC><bibtex> | ||
| + | @unpublished{ | ||
| + | author = {Florent Becker}, | ||
| + | title = {Strictly Self-Assembling Discrete Self-Similar Fractals Using Quines} | ||
| + | year = {2024}, | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | <ref name=UAV2HAM><bibtex> | ||
| + | @inproceedings{ICALP, | ||
| + | author = {David Cabellero and | ||
| + | Timothy Gomez and | ||
| + | Robert Schweller and | ||
| + | Tim Wylie}, | ||
| + | title = {Unique Assembly Verification in Two-Handed Self-Assembly} | ||
| + | booktitlev= {49th International Colloquium on Automata, Languages, and Programming (ICALP | ||
| + | 2022)}, | ||
| + | year = {2022}, | ||
| + | pages = {34:1-34:21} | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | <ref name=TEMP1NONTURING><bibtex> | ||
| + | @inproceedings{DNA, | ||
| + | author = {Pierre-Étienne Meunier and | ||
| + | Damien Regnault}, | ||
| + | title = {Directed Non-Cooperative Tile Assembly is Decidable} | ||
| + | booktitlev= {27th International Conference on DNA Computing and Molecular Programming (DNA | ||
| + | 27)}, | ||
| + | year = {2021}, | ||
| + | pages = {6:1-6:21} | ||
| + | } | ||
| + | </bibtex></ref> | ||
</references> | </references> | ||
[[Category: self-assembly]] | [[Category: self-assembly]] | ||
Latest revision as of 04:58, 24 July 2024
The following is a partial list of some of the many open problems in self-assembly:
- In his 1998 thesis [1], Winfree showed that the class of directed aTAM systems at temperature 2 is computationally universal, and in [2] Cook et al. showed that undirected temperature 1 aTAM systems could perform computations with a given amount of certainty. They also showed that in 2 planes directed aTAM temperature 1 systems are computationally universal. Is the class of directed aTAM systems at temperature 1 in the plane computationally universal? In [3] Doty, Patitz, and Summers provide insights into this question. SOLVED[4][5]
- Can \(n \times n\) squares efficiently self-assemble at temperature 1 (i.e. can less than \(O(n)\) tile types be used)?
- In [6], Doty et al. introduced a model known as the fuzzy temperature model and showed that in this model n by n squares could efficiently self-assemble. Can systems in this model also perform general computation?
- In Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue, Patitz et al. introduced the ``restricted glue TAM`` (rgTAM), a version of the aTAM in which a single glue whose strength is -1 (i.e. it is repulsive) is allowed, and all other glues must be strength 1. They showed that it is computationally universal. However, is a 2HAM version of the rgTAM also computationally universal? SOLVED[7]
- In [8] Doty et al. showed that the aTAM is intrinsically universal for itself, but for directed systems the intrinsically universal tile set fundamentally relies on nondeterminism. Is the class of directed aTAM systems intrinsically universal for itself? SOLVED[9]
- Is the STAM intrinsically universal for itself? Also, in [10] it was shown that the 3D aTAM is IU for a subset of the STAM, but it remains open whether or not adding negative strength glues allows the 3D aTAM to be IU for the full STAM. Additionally related to the STAM, for every Staged Assembly Model system is there an STAM system which can simulate it?
- Is the class of aTAM systems at temperature 1 intrinsically universal for itself? SOLVED[5]
- In his 1998 thesis [1], Winfree introduced both the aTAM and its more practical counterpart the kTAM. Currently, the 2HAM does not have a more realistic counterpart. Formulate a "k2HAM" model which takes into account the size of assemblies binding together (the bigger the assemblies the less likely it is they will bind together) and the lack of rigidity when assemblies come together.
- In Self-Assembly of Discrete Self-Similar Fractals, Patitz and Summers proved several results about self-assembling discrete self-similar fractals, but it is still an open questions as to whether or not there exists a discrete self-similar fractal that can be self-assembled in the aTAM. Also, are there discrete self-similar fractals which are not pinch-point fractals that are provably impossible to strictly self-assemble (e.g. the Sierpinski carpet)? SOLVED [11] [12]
- In Self-Assembly with Geometric Tiles, a construction was shown in which 2D tiles with disconnected geometries which are forced to stay within the plane as they combine, are capable of assembling n by n squares using only \(O(\log(\log(n)))\) tile types. Can a similar construction be shown with connected geometries (and staying in 2D)?
- In Computability and Complexity in Self-Assembly, it was shown that for every computably enumerable language \(L \subset \mathbb{N}\), a pattern representing \(L\) weakly self-assembles along the x-axis, but with the points spread out roughly quadratically. Can those points instead be spread out by only a constant factor? (Or with no space between them as with decidable languages as shown in Self-Assembly of Decidable Sets?)
- In One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece, Demaine et al. showed that it is possible to turn any aTAM system into a single rotatable (non-square) tile which simulates it. They also showed how to adapt this result to convert any of a variety of plane tiling systems (such as Wang tiles) into a "nearly" plane tiling system with a single tile (but with small gaps between the tiles). An open question is whether or not this can be improved to result in a system which fully tiles the plane. (This has been an open problem in tiling theory for many years.)
- In Two Hands Are Better Than One (up to constant factors), among other results, Cannon et al. proved that in the 3D 2HAM, if you are given a system \(\mathcal{T}\) and an assembly \(\alpha\), it is co-NP complete to determine if \(\alpha\) is the unique terminal assembly of \(\mathcal{T}\). It remains open what the complexity of this problem is in 2D. In the same paper, they showed how any aTAM system can be simulated by a 2HAM system at scale factor 5. It remains open how small this scale factor can actually be. SOLVED[13]
- ↑ 1.0 1.1
Erik Winfree - Algorithmic Self-Assembly of DNA
- Ph.D. Thesis, California Institute of Technology , June 1998
- BibtexAuthor : Erik Winfree
Title : Algorithmic Self-Assembly of DNA
In : Ph.D. Thesis, California Institute of Technology -
Address :
Date : June 1998
- ↑
Matthew Cook, Yunhui Fu, Robert T. Schweller - Temperature 1 Self-Assembly: Deterministic Assembly in 3{D} and Probabilistic Assembly in 2{D}
- SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms ,2011
- BibtexAuthor : Matthew Cook, Yunhui Fu, Robert T. Schweller
Title : Temperature 1 Self-Assembly: Deterministic Assembly in 3{D} and Probabilistic Assembly in 2{D}
In : SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms -
Address :
Date : 2011
- ↑
David Doty, Matthew J. Patitz, Scott M. Summers - Limitations of Self-Assembly at Temperature 1
- Theoretical Computer Science 412:145-158,2011
- BibtexAuthor : David Doty, Matthew J. Patitz, Scott M. Summers
Title : Limitations of Self-Assembly at Temperature 1
In : Theoretical Computer Science -
Address :
Date : 2011
- ↑
Pierre-Étienne Meunier, Damien Regnault - Directed Non-Cooperative Tile Assembly is Decidable
- ↑ 5.0 5.1
Pierre-Étienne Meunier, Damien Woods - The non-cooperative tile assembly model is not intrinsically
universal or capable of bounded Turing machine simulation
- ↑
David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, Scott M. Summers - Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature
- Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010) pp. 417--426,2010
- BibtexAuthor : David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, Scott M. Summers
Title : Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature
In : Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010) -
Address :
Date : 2010
- ↑
Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Andrew Winslow - Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly
- ↑
David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods - The tile assembly model is intrinsically universal
- Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science ,2012
- BibtexAuthor : David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods
Title : The tile assembly model is intrinsically universal
In : Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science -
Address :
Date : 2012
- ↑
Pierre-Étienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, Damien Woods - Intrinsic universality in tile self-assembly requires cooperation
- ↑
Jacob Hendricks, Jennifer E. Padilla, Matthew J. Patitz, Trent A. Rogers - Signal Transmission across Tile Assemblies: 3D Static Tiles
Simulate Active Self-assembly by 2D Signal-Passing Tiles
- DNA Computing and Molecular Programming - 19th International Conference, DNA 19, Tempe, AZ, USA, September 22-27, 2013. Proceedings pp. 90-104,2013
- BibtexAuthor : Jacob Hendricks, Jennifer E. Padilla, Matthew J. Patitz, Trent A. Rogers
Title : Signal Transmission across Tile Assemblies: 3D Static TilesSimulate Active Self-assembly by 2D Signal-Passing Tiles
Proceedings -
In : DNA Computing and Molecular Programming - 19th International Conference, DNA 19, Tempe, AZ, USA, September 22-27, 2013.
Address :
Date : 2013
- ↑
- Strictly Self-Assembling Discrete Self-Similar Fractals Using Quines
- ↑
- Strictly Self-Assembling Discrete Self-Similar Fractals Using Quines
- ↑
David Cabellero, Timothy Gomez, Robert Schweller, Tim Wylie - Unique Assembly Verification in Two-Handed Self-Assembly
