by Yuriy Brun

Abstract:

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 $\Theta(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 probability can be made arbitrarily close to 1.

Citation:

Yuriy Brun, Nondeterministic polynomial time factoring in the tile assembly model, Theoretical Computer Science, vol. 395, no. 1, April 2008, pp. 3–23.

Related:

A previous version appeared as University of Southern California,
Center for Software Engineering technical report USC-CSSE-2007-707.

Bibtex:

@article{Brun08factor, author = {Yuriy Brun}, title = {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun08factor.pdf}{Nondeterministic polynomial time factoring in the tile assembly model}}, journal = {Theoretical Computer Science}, venue = {TCS}, volume = {395}, number = {1}, pages = {3--23}, month = {April}, date = {17}, year = {2008}, issn = {0304-3975}, doi = {10.1016/j.tcs.2007.07.051}, publisher = {Elsevier}, address = {Essex, {UK}}, note = {A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2007-707. \href{http://dx.doi.org/10.1016/j.tcs.2007.07.051}{DOI: 10.1016/j.tcs.2007.07.051}}, previous = {A previous version appeared as University of Southern California, Center for Software Engineering technical report USC-CSSE-2007-707.}, abstract = {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 $\Theta(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 probability can be made arbitrarily close to 1.}, }