Efficient 3-SAT Algorithms in the Tile Assembly Model

Abstract 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 imple-mentations and distributed computational software sys-tems. 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 SFS; a tile system that decides 3-SAT by creating OHð1:8393nÞ nondeterministic assemblies in parallel, improving on the previous best known solution that requires Hð2nÞ 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 Hð1Þ; and that the assembly time is nondetermin-istic linear in the size of the input