Complexities for the design of self-assembly systems.

摘要

Self-assembly is the process by which objects autonomously assemble into complexes. It is believed that self-assembly technology will ultimately permit the precise fabrication of complex nanostructures. Of particular interest are self-assembly systems that are highly programmable. That is, we can view a self-assembly system as analogous to a program, the process of self-assembly as computation, and the resultant structure or shape assembled as the output. In this context, we are interested in the design of compact systems for the efficient assembly of desired target structures.; In this dissertation I present theoretical work in the area of self-assembly, focusing primarily on DNA self-assembly and the tile assembly model framework. I introduce a collection of new, natural models of self-assembly and show how these models affect the power of self-assembly. In doing so, we introduce new programming paradigms for self-assembly such as temperature programming . We further consider computational problems related to the design of self-assembly systems, including assembly verification and DNA strand design. For various formulations of these problems, we provide either efficient algorithmic solutions, or proofs of computational hardness.