Nondeterministic polynomial time factoring in the tile assembly model
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.},
}