کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436427 690001 2008 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Nondeterministic polynomial time factoring in the tile assembly model
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Nondeterministic polynomial time factoring in the tile assembly model
چکیده انگلیسی

Formalized study of self-assembly has led to the definition of the tile assembly model, Previously I presented ways to compute arithmetic functions, such as addition and multiplication, in 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. Here, I present tile assembly model systems that factor numbers nondeterministically using Θ(1) distinct components. The computation takes advantage of nondeterminism, but theoretically, each of the nondeterministic paths is executed in parallel, yielding the solution in time linear in the size of the input, with high probability. I describe mechanisms for finding the successful solutions among the many parallel executions and explore bounds on the probability of such a nondeterministic system succeeding and prove that the probability can be made arbitrarily close to 1.

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