@article{Brun12natcomp,
  title =
  {Efficient
  3-{SAT} algorithms in the tile assembly model},
  author = {Yuriy Brun},
  journal = {Natural Computing},
  venue = {NatComp},
  volume = {11},
  number = {2},
  pages = {209--229},
  year = {2012},
  doi = {10.1007/s11047-011-9299-0},

  note = {Extended and revised version of\ref{Brun11dna-lncs}.
  DOI:
  10.1007/s11047-011-9299-0},

  previous = {Extended and revised version of "Improving efficiency of
  3-SAT-solving tile systems" in DNA Computing 2011.},

  abstract = {Self-assembly is a powerful process found in nature that guides
  simple objects assembling, on their own, into complex structures.
  Self-assembly is of interest to computer scientists because self-assembling
  systems can compute functions, assemble shapes, and guide distributed
  robotics systems. The tile assembly model is a formal mathematical model of
  self-assembly that allows the study of time and space complexities of
  self-assembling systems that lie at the heart of several molecular computer
  implementations and distributed computational software systems. These
  implementations and systems require efficient tile systems with small
  tilesets and fast execution times. The state of the art, however, requires
  vastly complex tile systems with large tilesets to implement fast
  algorithms.

  In this paper, I present a tile system that decides 3-SAT by creating
  $O^\star(1.8393^n)$ nondeterministic assemblies in parallel, improving on
  the previous best known solution that requires $\Theta(2^n)$ such
  assemblies. This solution directly improves the feasibility of building
  molecular 3-SAT solvers and efficiency of distributed software. I formally
  prove the correctness of the system, the number of required parallel
  assemblies, that the size of the system's tileset is $147 = \Theta(1)$, and
  that the assembly time is nondeterministic linear in the size of the
  input.},
}