Nondeterministic polynomial time factoring in the tile assembly model

作     者：Brun, Yuriy 

作者机构：Univ So Calif Dept Comp Sci Los Angeles CA 90089 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2008年第395卷第1期

页      面：3-23页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：self-assembly factoring tile assembly model crystal growth molecular computation natural computation distributed computing parallel computing nondeterministic computation 

摘      要：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 e(l) 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. (C) 2007 Elsevier B.V. All rights reserved.