We present a theoretical model for self-assembling tiles with flexible branches motivated by DNA branched junction molecules. We encode an instance of a "problem" as a pot of such tiles, and a "solution" as an assembled complete complex without any free sticky ends (called ports), whose number of tiles is within predefined bounds. We develop an algebraic representation of this self-assembly process and use it to prove that this model of self-assembly precisely captures NP-computability when the number of tiles in the minimal complete complexes is bounded by a polynomial.
展开▼
