by Yuriy Brun

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 ın \mathbbN$, 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.

Citation:

Yuriy Brun, Reducing tileset size: 3-SAT and beyond, in Proceedings of the 14th International Meeting on DNA Computing (DNA), 2008, pp. 178.

Related:

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

Bibtex:

@inproceedings{Brun08dna-sat, author = {Yuriy Brun}, title = {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun08dna-sat.pdf}{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.}, }