@article{Brun08dna-lncs,
  author = {Yuriy Brun},
  title =
  {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun08dna-lncs.pdf}{Constant-size
  tileset for solving an {NP}-complete problem in nondeterministic linear
  time}},
  journal = {Lecture Notes on Computer Science},
  booktitle = {{DNA} Computing},
  venue = {DNA},
  volume = {4848/2008},
  pages = {26--35},
  year = {2008},
  issn = {0302-9743},
  isbn = {978-3-540-77961-2},
  doi = {10.1007/978-3-540-77962-9_3},
  publisher = {Springer Berlin / Heidelberg},
  editor = {Max Garzon and Hao Yan},

  note = {Extended and revised in~\ref{Brun08sat}. A previous version
  appeared as ``Asymptotically Optimal Program Size Complexity for Solving
  {NP}-Complete Problems in the Tile Assembly Model'' in the Proceedings of the
  13th International Meeting on {DNA} Computing ({DNA}07), pages 231--240, 2007.
  \href{https://doi.org/10.1007/978-3-540-77962-9\_3}{DOI:
  10.1007/978-3-540-77962-9\_3}},
  
  previous = {Extended and revised in "Constant-size tileset for solving an
  {NP}-complete problem in nondeterministic linear time" in the Journal of
  Algorithms. A previous version appeared as "Asymptotically Optimal Program
  Size Complexity for Solving NP-Complete Problems in the Tile Assembly Model"
  in the Proceedings of the 13th International Meeting on DNA Computing, pp.
  231–240, 2007.},

  abstract = {The tile assembly model, a formal model of crystal growth, is of
  special interest to computer scientists and mathematicians because it is
  universal. Therefore, tile assembly model systems can compute all the
  functions that computers compute. In this paper, I formally define what it
  means for a system to nondeterministically decide a set, and present a system
  that solves an NP-complete problem called $\mathit{SubsetSum}$. Because of the
  nature of NP-complete problems, this system can be used to solve all NP
  problems in polynomial time, with high probability. While the proof that the
  tile assembly model is universal implies the construction of such systems,
  those systems are in some sense ``large'' and ``slow.'' The system presented
  here uses $49 = \Theta(1)$ different tiles and computes in time linear in the
  input size. I also propose how such systems can be leveraged to program large
  distributed software systems.},
}