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~\ref{Brun08dna-sat}. A
previous version appeared as University of Southern California, Center for
Software Engineering technical report USC-CSSE-2008-801.
\href{https://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$.}
}