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 \(\mathbb{S}_{\mathit{FS}}\), a tile system that decides 3-\(\mathit{SAT}\) by creating O ⋆ (1.8393n) nondeterministic assemblies in parallel, while the previous best known solution requires Θ(2n) 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 ⋆ (1.8393n), that the size of the system’s tileset is 147 = Θ(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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abelson, H., Allen, D., Coore, D., Hanson, C., Homsy, G., Knight Jr., T.F., Nagpal, R., Rauch, E., Sussman, G.J., Weiss, R.: Amorphous computing. Communications of the ACM 43(5), 74–82 (2000)
Adleman, L.: Towards a mathematical theory of self-assembly. Tech. Rep. 00-722, Department of Computer Science, University of Southern California, Los Angeles, CA (2000)
Barish, R., Rothemund, P.W.K., Winfree, E.: Two computational primitives for algorithmic self-assembly: Copying and counting. Nano Letters 5(12), 2586–2592 (2005)
Brun, Y.: Arithmetic computation in the tile assembly model: Addition and multiplication. Theoretical Computer Science 378(1), 17–31 (2007)
Brun, Y.: Nondeterministic polynomial time factoring in the tile assembly model. Theoretical Computer Science 395(1), 3–23 (2008)
Brun, Y.: Solving NP-complete problems in the tile assembly model. Theoretical Computer Science 395(1), 31–46 (2008)
Brun, Y.: Solving satisfiability in the tile assembly model with a constant-size tileset. Journal of Algorithms 63(4), 151–166 (2008)
Brun, Y., Medvidovic, N.: Preserving privacy in distributed computation via self-assembly. Tech. Rep. USC-CSSE-2008-819, Center for Software Engineering, University of Southern California (2008)
Kullmann, O.: Worst-case analysis, 3-SAT decision and lower bounds: Approaches for improved SAT algorithms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35, 261–313 (1997)
Kullmann, O.: New methods for 3-SAT decisions and worst-case analysis. Theoretical Computer Science 223, 1–72 (1999)
Lagoudakis, M.G., LaBean, T.H.: 2D DNA self-assembly for satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 54, 141–154 (1999)
McLurkin, J., Smith, J., Frankel, J., Sotkowitz, D., Blau, D., Schmidt, B.: Speaking swarmish: Human-robot interface design for large swarms of autonomous mobile robots. In: Proceedings of the AAAI Spring Symposium, Stanford, CA, USA (March 2006)
Monien, B., Speckenmeyer, E.: Solving satisfiability in less than 2n steps. Discrete Applied Mathematics 10(3), 287–296 (1985)
Rothemund, P.W.K., Papadakis, N., Winfree, E.: Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biology 2(12), e424 (2004)
Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), Portland, OR, USA, May 2000, pp. 459–468 (2000)
Schiermeyer, I.: Solving 3-satisfiability in less than 1.579n steps. Computer Science Logic 702, 379–394 (1993)
Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. SIAM Journal on Computing 36(6), 1544–1569 (2007)
Wang, H.: Proving theorems by pattern recognition. II. Bell System Technical Journal 40, 1–42 (1961)
Winfree, E.: Algorithmic Self-Assembly of DNA. Ph.D. thesis, California Institute of Technology, Pasadena, CA, USA (June 1998)
Winfree, E.: Simulations of computing by self-assembly of DNA. Tech. Rep. CS-TR:1998:22, California Institute of Technology, Pasadena, CA, USA (1998)
Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. Combinatorial Optimization - Eureka, You Shrink! pp. 185–207 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brun, Y. (2011). Improving Efficiency of 3-SAT-Solving Tile Systems. In: Sakakibara, Y., Mi, Y. (eds) DNA Computing and Molecular Programming. DNA 2010. Lecture Notes in Computer Science, vol 6518. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18305-8_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-18305-8_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-18304-1
Online ISBN: 978-3-642-18305-8
eBook Packages: Computer ScienceComputer Science (R0)