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}, }