Solving NP-complete problems in the tile assembly model

Brun, Yuriy

doi:10.1016/j.tcs.2007.07.052

by Yuriy Brun

Abstract:

Formalized study of self-assembly has led to the definition of the tile assembly model, a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Previously, I defined deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply, and factor. Here, I extend the notion of computation to include deciding subsets of the natural numbers, and present a system that decides $\mathitSubsetSum$, 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: 49. 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.

View PDF

Citation:

Yuriy Brun, Solving NP-complete problems in the tile assembly model, Theoretical Computer Science, vol. 395, no. 1, April 2008, pp. 31–46.

Extended and revised version of "Constant-size tileset for solving an NP-complete problem in nondeterministic linear time" in DNA Computing 2008. A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2007-703.

Bibtex:

@article{Brun08np-c,
  author = {Yuriy Brun},
  title =
  {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun08np-c.pdf}{Solving
  {NP}-complete problems in the tile assembly model}},
  journal = {Theoretical Computer Science},
  venue = {TCS},
  volume = {395},
  number = {1},
  pages = {31--46},
  month = {April},
  date = {17},
  year = {2008},
  issn = {0304-3975},
  doi = {10.1016/j.tcs.2007.07.052},
  publisher = {Elsevier},
  address = {Essex, {UK}},

  note = {Extended and revised version of~\ref{Brun08dna-lncs}. A
  previous version appeared as University of Southern California, Center for
  Software Engineering technical report USC-CSSE-2007-703.
  \href{https://doi.org/10.1016/j.tcs.2007.07.052}{DOI:
  10.1016/j.tcs.2007.07.052}},

  previous = {Extended and revised version of "Constant-size tileset for solving
  an NP-complete problem in nondeterministic linear time" in DNA Computing 2008.
  A previous version appeared as University of Southern California, Center for
  Software Engineering technical report USC-CSSE-2007-703.},

  abstract = {Formalized study of self-assembly has led to the definition of the
  tile assembly model, a highly distributed parallel model of computation that
  may be implemented using molecules or a large computer network such as the
  Internet. Previously, I defined deterministic and nondeterministic computation
  in the tile assembly model and showed how to add, multiply, and factor. Here,
  I extend the notion of computation to include deciding subsets of the natural
  numbers, and present a system that decides $\mathit{SubsetSum}$, 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: 49. 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.},
}