Difference between revisions of "Solving np-complete Problems in the Tile Assembly Model"
m |
|||
Line 4: | Line 4: | ||
computation that may be implemented using molecules or a large computer network such as the Internet. Previously, I defined | computation that may be implemented using molecules or a large computer network such as the Internet. Previously, I defined | ||
deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply and factor. Here, I | deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply and factor. Here, I | ||
− | extend the notion of computation to include deciding subsets of the natural numbers, and present a system that decides \textit{SubsetSum}, | + | extend the notion of computation to include deciding subsets of the natural numbers, and present a system that decides $\textit{SubsetSum}$, |
a well-known NP-complete problem. The computation is nondeterministic and each parallel assembly executes in time linear in | a well-known NP-complete problem. The computation is nondeterministic and each parallel assembly executes in time linear in | ||
the input. The system requires only a constant number of different tile types: 49. I describe mechanisms for finding the successful | the input. The system requires only a constant number of different tile types: 49. I describe mechanisms for finding the successful |
Latest revision as of 10:07, 14 June 2022
Published on: 2008/04/17
Abstract
Formalized study of self-assembly has led to the definition of the tile assembly model, a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Previously, I defined deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply and factor. Here, I extend the notion of computation to include deciding subsets of the natural numbers, and present a system that decides \(\textit{SubsetSum}\), a well-known NP-complete problem. The computation is nondeterministic and each parallel assembly executes in time linear in the input. The system requires only a constant number of different tile types: 49. I describe mechanisms for finding the successful solutions among the many parallel assemblies and explore bounds on the probability of such a nondeterministic system succeeding and prove that probability can be made arbitrarily close to one.
Authors
Yuriy Brun