×

On the computational power of DNA. (English) Zbl 0906.68071

Summary: We show how DNA-based computers can be used to solve the satisfiability problem for Boolean circuits. Furthermore, we show how DNA computers can solve optimization problems directly without first solving several decision problems. Our methods also enable random sampling of satisfying assignments.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
92D20 Protein sequences, DNA sequences

Keywords:

DNA computers
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Adleman, L., Molecular computation of solutions to combinatorial problems, Science, 266, 1021-1024 (1994)
[2] L. Adleman, On constructing a molecular computer, Proceedings of the 1st DIMACS Workshop on DNA Computing.; L. Adleman, On constructing a molecular computer, Proceedings of the 1st DIMACS Workshop on DNA Computing.
[3] M. Amos, A. Gibbons and D. Hodgson, Error-resistant implementation of DNA computations, Unpublished manuscript.; M. Amos, A. Gibbons and D. Hodgson, Error-resistant implementation of DNA computations, Unpublished manuscript. · Zbl 0919.68030
[4] Bach, E.; Condon, A.; Glaser, E.; Tanguay, C., DNA models and algorithms for NP-complete problems, (Proceedings of the 11th Annual IEEE Conference on Computational Complexity (1996)) · Zbl 0921.68028
[5] Beaver, D., A universal molecular computer, (Tech. Report CSE-95-001 (1995), Penn State University)
[6] Also in Proceedings of 1st DIMACS Workshop on DNA Computing.; Also in Proceedings of 1st DIMACS Workshop on DNA Computing.
[7] Boneh, D.; Dunworth, C.; Lipton, R. J.; Sgall, J., On the computational power of DNA, (Tech. Report CS-TR-499-95 (1995), Princeton University) · Zbl 0906.68071
[8] Boneh, D.; Lipton, R. J., Making DNA computers error resistant, (Tech. Report CS-TR-491-95 (1995), Princeton University) · Zbl 0919.68031
[9] D. Boneh, R.J. Lipton and J. Sgall, Error resistant and uniform DNA computers, in preparation.; D. Boneh, R.J. Lipton and J. Sgall, Error resistant and uniform DNA computers, in preparation. · Zbl 0919.68031
[10] Jerrum, M.; Valiant, L.; Vazirani, U., Random generation of combinatorial structures from a uniform distribution, Theoret. Comput Sci., 43, 169-188 (1986) · Zbl 0597.68056
[11] Kannan, R., Markov chains and polynomial time algorithms, (Proceedings of the 35th Annual Symposium on Foundations of Computer Science (1994), IEEE: IEEE New York), 656-671
[12] Karp, R.; Kenyon, C.; Waarts, O., Error-resilient DNA computations, (Proceedings of SODA (1996)), 458-467 · Zbl 0846.68034
[13] Lipton, R. J., Using DNA to solve NP-complete problems, Science, 268, 542-545 (1995)
[14] C. Papadimitriou, private communications.; C. Papadimitriou, private communications.
[15] Reif, J., Parallel molecular computation, (Proceedings of 7th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’95) (1995)), 213-223
[16] Robson, J., Algorithms for maximum independent sets, J. Algorithms, 7, 425-440 (1986) · Zbl 0637.68080
[17] Rooβ, D.; Wagner, K. W., On the power of bio-computers, (Tech. Report (1995), University of Würzburg)
[19] Smith, W.; Schweitzer, A., DNA computers in vitro and vivo, (Tech. Report (1995), NEC)
[20] Stockmeyer, L., On approximating algorithms for # P, SIAM J. Comput., 14, 849-861 (1985) · Zbl 0589.68031
[21] Tarjan, R.; Trojanowsky, A., Finding a maximum independent set, SIAM J. Comput., 6, 537-546 (1977) · Zbl 0357.68035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.