by Yuriy Brun

Abstract:

The tile assembly model, a formal model of crystal growth, is of special interest to computer scientists and mathematicians because it is universal. Therefore, tile assembly model systems can compute all the functions that computers compute. In this paper, I formally define what it means for a system to nondeterministically decide a set, and present a system that solves an NP-complete problem called $\mathitSubsetSum$. Because of the nature of NP-complete problems, this system can be used to solve all NP problems in polynomial time, with high probability. While the proof that the tile assembly model is universal implies the construction of such systems, those systems are in some sense ``large'' and ``slow.'' The system presented here uses $49 = \Theta(1)$ different tiles and computes in time linear in the input size. I also propose how such systems can be leveraged to program large distributed software systems.

Citation:

Yuriy Brun, Constant-size tileset for solving an NP-complete problem in nondeterministic linear time, Lecture Notes on Computer Science, vol. 4848/2008, 2008, pp. 26–35.

Related:

Extended and revised in "Constant-size tileset for solving an
{NP}-complete problem in nondeterministic linear time" in the Journal of
Algorithms. A previous version appeared as "Asymptotically Optimal Program
Size Complexity for Solving NP-Complete Problems in the Tile Assembly Model"
in the Proceedings of the 13th International Meeting on DNA Computing, pp.
231–240, 2007.

Bibtex:

@article{Brun08dna-lncs, author = {Yuriy Brun}, title = {\href{http://people.cs.umass.edu/brun/pubs/pubs/Brun08dna-lncs.pdf}{Constant-size tileset for solving an {NP}-complete problem in nondeterministic linear time}}, journal = {Lecture Notes on Computer Science}, booktitle = {{DNA} Computing}, venue = {DNA}, volume = {4848/2008}, pages = {26--35}, year = {2008}, issn = {0302-9743}, isbn = {978-3-540-77961-2}, doi = {10.1007/978-3-540-77962-9_3}, publisher = {Springer Berlin / Heidelberg}, editor = {Max Garzon and Hao Yan}, note = {Extended and revised in~\ref{Brun08sat}. A previous version appeared as ``Asymptotically Optimal Program Size Complexity for Solving {NP}-Complete Problems in the Tile Assembly Model'' in the Proceedings of the 13th International Meeting on {DNA} Computing ({DNA}07), pages 231--240, 2007. \href{https://doi.org/10.1007/978-3-540-77962-9\_3}{DOI: 10.1007/978-3-540-77962-9\_3}}, previous = {Extended and revised in "Constant-size tileset for solving an {NP}-complete problem in nondeterministic linear time" in the Journal of Algorithms. A previous version appeared as "Asymptotically Optimal Program Size Complexity for Solving NP-Complete Problems in the Tile Assembly Model" in the Proceedings of the 13th International Meeting on DNA Computing, pp. 231–240, 2007.}, abstract = {The tile assembly model, a formal model of crystal growth, is of special interest to computer scientists and mathematicians because it is universal. Therefore, tile assembly model systems can compute all the functions that computers compute. In this paper, I formally define what it means for a system to nondeterministically decide a set, and present a system that solves an NP-complete problem called $\mathit{SubsetSum}$. Because of the nature of NP-complete problems, this system can be used to solve all NP problems in polynomial time, with high probability. While the proof that the tile assembly model is universal implies the construction of such systems, those systems are in some sense ``large'' and ``slow.'' The system presented here uses $49 = \Theta(1)$ different tiles and computes in time linear in the input size. I also propose how such systems can be leveraged to program large distributed software systems.}, }