by Yuriy Brun
Abstract:
The tile assembly model has allowed the study of the nature's process of self-assembly and the development of self-assembling systems for solving complex computational problems. Research into this model has led to progress in two distinct classes of computational systems: Internet-sized distributed computation, such as software architectures for computational grids, and molecular computation, such as DNA computing. The design of large complex tile systems that emulate Turing machines has shown that the tile assembly model is Turing universal, while the design of small tile systems that implement simple algorithms has shown that tile assembly can be used to build private, fault-tolerant, and scalable distributed software systems and robust molecular machines. However, in order for these types of systems to compete with traditional computing devices, we must demonstrate that fairly simple tile systems can implement complex and intricate algorithms for important problems. The state of the art, however, requires vastly complex tile systems with large tile sets to implement such algorithms. In this paper, I present a tile system that decides 3-SAT by creating $O^\star\left(1.8393^n\right)$ nondeterministic assemblies in parallel, while the previous best known solution requires $\Theta\left(2^n\right)$ such assemblies. In some sense, this tile system follows the most complex algorithm implemented using tiles to date. I analyze that the number of required parallel assemblies is $O^\star\left(1.8393^n\right)$, 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. This work directly improves the time and space complexities of tile-inspired computational-grid architectures and bridges theory and today's experimental limitations of DNA computing.
Citation:
Yuriy Brun, Improving efficiency of 3-SAT-solving tile systems, Lecture Notes on Computer Science, vol. 6518/2011, 2011, pp. 1–12.
Related:
Extended and revised in "Efficient 3-SAT algorithms in the tile
assembly model" in Natural Computing. A previous version appeared in the
Proceedings of the 16th International Conference on DNA Computing, pp.
70–81, 2010.
Bibtex:
@article{Brun11dna-lncs,
author = {Yuriy Brun},
title =
{\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun11dna-lncs.pdf}{Improving
efficiency of 3-{SAT}-solving tile systems}},
journal = {Lecture Notes on Computer Science},
booktitle = {{DNA} Computing},
venue = {DNA},
volume = {6518/2011},
pages = {1--12},
year = {2011},
doi = {10.1007/978-3-642-18305-8_1},
note = {Extended and revised in~\ref{Brun12natcomp}. A previous
version appeared in the Proceedings of the 16th International Conference on
{DNA} Computing ({DNA}10), pages 70--81, 2010.
\href{https://doi.org/10.1007/978-3-642-18305-8\_1}{DOI:
10.1007/978-3-642-18305-8\_1}},
previous = {Extended and revised in "Efficient 3-SAT algorithms in the tile
assembly model" in Natural Computing. A previous version appeared in the
Proceedings of the 16th International Conference on DNA Computing, pp.
70–81, 2010.},
abstract = {The tile assembly model has allowed the study of the nature's
process of self-assembly and the development of self-assembling systems for
solving complex computational problems. Research into this model has led to
progress in two distinct classes of computational systems: Internet-sized
distributed computation, such as software architectures for computational
grids, and molecular computation, such as DNA computing. The design of large
complex tile systems that emulate Turing machines has shown that the tile
assembly model is Turing universal, while the design of small tile systems
that implement simple algorithms has shown that tile assembly can be used to
build private, fault-tolerant, and scalable distributed software systems and
robust molecular machines. However, in order for these types of systems to
compete with traditional computing devices, we must demonstrate that fairly
simple tile systems can implement complex and intricate algorithms for
important problems. The state of the art, however, requires vastly complex
tile systems with large tile sets to implement such algorithms.
In this paper, I present a tile system that decides 3-SAT by creating
$O^\star\left(1.8393^n\right)$ nondeterministic assemblies in parallel,
while the previous best known solution requires $\Theta\left(2^n\right)$
such assemblies. In some sense, this tile system follows the most complex
algorithm implemented using tiles to date. I analyze that the number of
required parallel assemblies is $O^\star\left(1.8393^n\right)$, 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. This work directly
improves the time and space complexities of tile-inspired computational-grid
architectures and bridges theory and today's experimental limitations of DNA
computing.},
fundedBy = {NSF CNS-0937060 to the CRA for the CIFellows Project},
}