Complexity classes for self-assembling flexible tiles

We present a theoretical model for self-assembling DNA tiles with flexible branches. We encode an instance of a “problem” as a pot of such tiles for which a “solution” is an assembled complete complex without any free sticky ends. Using the number of tiles in an assembled complex as a measure of complexity we show how NTIME classes (such as NP and NEXP) can be represented with corresponding classes of the model.

Authors

• Nataša Jonoska
• Gregory L. McColm

Keywords

• Self-assembly
• DNA junction molecules
• DNA-based graph structures
• Assembling complexes
• Complexity classes of self-assembly