کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436429 690001 2008 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solving NP-complete problems in the tile assembly model
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Solving NP-complete problems in the tile assembly model
چکیده انگلیسی

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 , 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 395, Issue 1, 17 April 2008, Pages 31-46