@inproceedings{Brun08dna-sat,
  author = {Yuriy Brun},
  title =
  {Reducing
  tileset size: 3-{SAT} and beyond},
  booktitle = {Proceedings of the 14th International Meeting on {DNA}
  Computing (DNA)},
  venue = {DNA},
  month = {June},
  date = {2--6},
  year = {2008},
  pages = {178},
  address = {Prague, Czech Republic},

  note = {Extended and revised in\ref{Brun08sat}},

  previous = {Extended and revised in "Constant-size tileset for solving an
  NP-complete problem in nondeterministic linear time" in the Journal of
  Algorithms.},

  abstract = {In self-assembly research, reducing the number of distinct tiles
  necessary to compute functions can make it feasible to implement tile systems
  to solve complex problems. Existing methods for solving 3-SAT, a well-known
  NP-complete problem, in the tile assembly model involve either using
  $\Theta(n^2)$ distinct tiles to nondeterministically decide whether an
  $n$-variable Boolean formula is satisfiable or simulating a cellular automata
  system simulating a Turing machine, which requires a constant but large number
  of tiles to deterministically make the decision. Here, I propose a system that
  solves k-SAT nondeterministically, for all $k \in \mathbb{N}$, in time linear
  in the input size using only 64 distinct tiles. Further, I propose a mechanism
  for converting the tilesets of tile systems for many NP-complete and other
  problems from tilesets whose size depends on the input into $\Theta(1)$-size
  tilesets.},
}