Improving efficiency of 3-SAT-solving tile systems
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~\cite{}{Brun12natcomp}. A previous
  version appeared in the Proceedings of the 16th International Conference on
  {DNA} Computing ({DNA}10), pages 70--81, 2010.
  \href{http://dx.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},
}