Difference between revisions of "Open Problems"

From self-assembly wiki
Jump to navigation Jump to search
(Created page with "Coming Soon as of 5/20/13! Category: self-assembly")
 
(Marked open problems which have been solved, with references)
 
(28 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
Coming Soon as of 5/20/13!
+
The following is a partial list of some of the many open problems in self-assembly:
 +
<br>
 +
<br>
 +
<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>
 +
 +
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 [[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>
 +
 +
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 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 [[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 [[Computability and Complexity in Self-Assembly]], it was shown that for every computably enumerable language $L \subset \mathbb{N}$, a pattern representing $L$ [[Weak_Self-Assembly | 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]]?)</li>
 +
 +
<li>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.)</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>
 +
 +
<ref name =Winf98><bibtex>
 +
@phdthesis{Winf98,
 +
  author = "Erik Winfree",
 +
  title = "Algorithmic Self-Assembly of DNA",
 +
  school = "California Institute of Technology",
 +
  year = "1998",
 +
  month = "June",
 +
}
 +
</bibtex></ref>
 +
 +
<ref name =jLSAT1><bibtex>
 +
@article{jLSAT1,
 +
  author =  "David Doty and Matthew J. Patitz and Scott M. Summers",
 +
  title =    "Limitations of Self-Assembly at Temperature 1",
 +
  journal = "Theoretical Computer Science",
 +
  volume = "412",
 +
  issue = "1-2",
 +
  pages="145-158",
 +
  year = "2011"
 +
}
 +
</bibtex></ref>
 +
 +
<ref name =CooFuSch11><bibtex>
 +
@inproceedings{CooFuSch11,
 +
  author = "Matthew Cook and Yunhui Fu and Robert T. Schweller",
 +
  title = "Temperature 1 Self-Assembly: Deterministic Assembly in 3{D} and Probabilistic Assembly in 2{D}",
 +
  year = 2011,
 +
  booktitle =  {SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms},
 +
  publisher =  {SIAM},
 +
}
 +
</bibtex></ref>
 +
 +
<ref name =SFTSAFT><bibtex>
 +
@inproceedings{SFTSAFT,
 +
  author = "David Doty and Matthew J. Patitz and Dustin Reishus and Robert T. Schweller and Scott M. Summers",
 +
  title = "Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature",
 +
  year = 2010,
 +
  booktitle = "Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)",
 +
  pages = "417--426"
 +
}
 +
</bibtex></ref>
 +
 +
<ref name =IUSA><bibtex>
 +
@inproceedings{IUSA,
 +
author    = {David Doty and
 +
              Jack H. Lutz and
 +
              Matthew J. Patitz and
 +
              Robert T. Schweller and
 +
              Scott M. Summers and
 +
              Damien Woods},
 +
title    = {The tile assembly model is intrinsically universal},
 +
booktitle = {Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science},
 +
series = {FOCS 2012},
 +
year = {2012},
 +
location = {New Brunswick, New Jersey},
 +
}
 +
</bibtex></ref>
 +
 +
<ref name =STAMIU><bibtex>
 +
@inproceedings{DBLP:conf/dna/HendricksPPR13,
 +
  author    = {Jacob Hendricks and
 +
              Jennifer E. Padilla and
 +
              Matthew J. Patitz and
 +
              Trent A. Rogers},
 +
  title    = {Signal Transmission across Tile Assemblies: 3D Static Tiles
 +
              Simulate Active Self-assembly by 2D Signal-Passing Tiles},
 +
  booktitle = {DNA Computing and Molecular Programming - 19th International
 +
              Conference, DNA 19, Tempe, AZ, USA, September 22-27, 2013.
 +
              Proceedings},
 +
  year      = {2013},
 +
  pages    = {90-104},
 +
  ee        = {http://dx.doi.org/10.1007/978-3-319-01928-4_7},
 +
  bibsource = {DBLP, http://dblp.uni-trier.de}
 +
}
 +
</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>
 
[[Category: self-assembly]]
 
[[Category: self-assembly]]

Latest revision as of 03:58, 24 July 2024

The following is a partial list of some of the many open problems in self-assembly:

Retrieved from "http://self-assembly.net/wiki/index.php?title=Open_Problems&oldid=2013"