@article{Brun08factor,
  author = {Yuriy Brun},
  title =
  {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.
  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.},
}