Solving satisfiability in the tile assembly model with a constant-size tileset
by Yuriy Brun
Abstract:
Biological systems are far more complex and robust than systems we can engineer today. One way to increase the complexity and robustness of our engineered systems is to study how biological systems function. The tile assembly model is a highly distributed parallel model of nature's self-assembly. Previously, I defined deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply, factor, and solve $\mathitSubsetSum$. Here, I present a system that decides satisfiability, a well-known NP-complete problem. The computation is nondeterministic and each parallel assembly executes in time linear in the input. The system requires only a constant number of different tile types: $64$, an improvement over previously best known system that uses $\Theta(n^2)$ tile types. I describe mechanisms for finding the successful solutions among the many parallel assemblies and explore bounds on the probability of such a nondeterministic system succeeding and prove that probability can be made arbitrarily close to $1$.
Citation:
Yuriy Brun, Solving satisfiability in the tile assembly model with a constant-size tileset, Journal of Algorithms, vol. 63, no. 4, 2008, pp. 151–166.
Related:
Extended and revised version of "Reducing tileset size: 3-SAT and beyond" in DNA Computing 2008. A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2008-801.
Bibtex:
@article{Brun08sat,
  author = {Yuriy Brun},
  title = {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun08sat.pdf}{Solving
  satisfiability in the tile assembly model with a constant-size tileset}},
  year = {2008},
  journal = {Journal of Algorithms},
  venue = {JAlg},
  volume = {63},
  number = {4},
  pages = {151--166},
  issn = {0196-6774},
  doi = {10.1016/j.jalgor.2008.07.002},
  publisher = {Academic Press, Inc.},
  address = {Duluth, MN, USA},

  note = {Extended and revised version of~\cite{}{Brun08dna-sat}. A
  previous version appeared as University of Southern California, Center for
  Software Engineering technical report USC-CSSE-2008-801.
  \href{http://dx.doi.org/10.1016/j.jalgor.2008.07.002}{DOI:
  10.1016/j.jalgor.2008.07.002}},

  previous = {Extended and revised version of "Reducing tileset size: 3-SAT and
  beyond" in DNA Computing 2008. A previous version appeared as University of
  Southern California, Center for Software Engineering technical report
  USC-CSSE-2008-801.},

  abstract = {Biological systems are far more complex and robust than systems we
  can engineer today. One way to increase the complexity and robustness of our
  engineered systems is to study how biological systems function. The tile
  assembly model is a highly distributed parallel model of nature's
  self-assembly. Previously, I defined deterministic and nondeterministic
  computation in the tile assembly model and showed how to add, multiply,
  factor, and solve $\mathit{SubsetSum}$. Here, I present a system that decides
  satisfiability, a well-known NP-complete problem. The computation is
  nondeterministic and each parallel assembly executes in time linear in the
  input. The system requires only a constant number of different tile types:
  $64$, an improvement over previously best known system that uses $\Theta(n^2)$
  tile types. I describe mechanisms for finding the successful solutions among
  the many parallel assemblies and explore bounds on the probability of such a
  nondeterministic system succeeding and prove that probability can be made
  arbitrarily close to $1$.} 
}