Self-assembly is a powerful process found in nature that guides simple objects assembling, on their own, into complex structures. Self-assembly is of interest to computer scientists because self-assembling systems can compute functions, assemble shapes, and guide distributed robotics systems. The tile assembly model is a formal mathematical model of self-assembly that allows the study of time and space complexities of self-assembling systems that lie at the heart of several molecular computer implementations and distributed computational software systems. These implementations and systems require efficient tile systems with small tilesets and fast execution times. The state of the art, however, requires vastly complex tile systems with large tilesets to implement fast algorithms.
In this paper, I present a tile system that decides 3-SAT by creating $O^\star(1.8393^n)$ nondeterministic assemblies in parallel, improving on the previous best known solution that requires $\Theta(2^n)$ such assemblies. This solution directly improves the feasibility of building molecular 3-SAT solvers and efficiency of distributed software. I formally prove the correctness of the system, the number of required parallel assemblies, that the size of the system's tileset is $147 = \Theta(1)$, and that the assembly time is nondeterministic linear in the size of the input.
@article{Brun12natcomp,
title =
{\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun12natcomp.pdf}{Efficient
3-{SAT} algorithms in the tile assembly model}},
author = {Yuriy Brun},
journal = {Natural Computing},
venue = {NatComp},
volume = {11},
number = {2},
pages = {209--229},
year = {2012},
doi = {10.1007/s11047-011-9299-0},
note = {Extended and revised version of~\ref{Brun11dna-lncs}.
\href{https://doi.org/10.1007/s11047-011-9299-0}{DOI:
10.1007/s11047-011-9299-0}},
previous = {Extended and revised version of "Improving efficiency of
3-SAT-solving tile systems" in DNA Computing 2011.},
abstract = {<p>Self-assembly is a powerful process found in nature that guides
simple objects assembling, on their own, into complex structures.
Self-assembly is of interest to computer scientists because self-assembling
systems can compute functions, assemble shapes, and guide distributed
robotics systems. The tile assembly model is a formal mathematical model of
self-assembly that allows the study of time and space complexities of
self-assembling systems that lie at the heart of several molecular computer
implementations and distributed computational software systems. These
implementations and systems require efficient tile systems with small
tilesets and fast execution times. The state of the art, however, requires
vastly complex tile systems with large tilesets to implement fast
algorithms.</p>
<p>In this paper, I present a tile system that decides 3-SAT by creating
$O^\star(1.8393^n)$ nondeterministic assemblies in parallel, improving on
the previous best known solution that requires $\Theta(2^n)$ such
assemblies. This solution directly improves the feasibility of building
molecular 3-SAT solvers and efficiency of distributed software. I formally
prove the correctness of the system, the number of required parallel
assemblies, that the size of the system's tileset is $147 = \Theta(1)$, and
that the assembly time is nondeterministic linear in the size of the
input.</p>},
}