کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429296 687176 2008 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solving satisfiability in the tile assembly model with a constant-size tileset
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Solving satisfiability in the tile assembly model with a constant-size tileset
چکیده انگلیسی

Biological systems are far more complex and robust than systems we can engineer today. One way to increase the complexity and robustness of our engineered systems is to study how biological systems function. The tile assembly model is a highly distributed parallel model of nature's self-assembly. Previously, I defined deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply, factor, and solve SubsetSum. Here, I present a system that decides satisfiability, 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: 64, an improvement over previously best known system that uses Θ(n2) tile types. 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 1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 63, Issue 4, October 2008, Pages 151-166