A parallel algorithm for solving sat problem based on dna computing

被引：1

作者：

Darehmiraki, M. ^{[1
]}

机构：

[1] Department of Mathematics, University of Birjand, Birjand

来源：

International Journal of Computers and Applications | 2009年 / 31卷 / 02期

关键词：

Dna computing; Np-complete; Sat problem;

D O I：

10.2316/Journal.202.2009.2.202-2502

中图分类号：

学科分类号：

摘要：

In this paper, stickers are used to construct a solution space of DNA for the satisfiability (SAT) problem. Simultaneously DNA operations are applied in the sticker-based model to develop a DNA algorithm. The result of the proposed algorithm shows that the SAT problem is resolved with biological operation in the sticker-based model for solution space of sticker. Furthermore, this work presents clear evidence of the ability of DNA computing to solve NP-complete problem. The potential of DNA computing for the SAT problem is promising, given the operational time complexity of O(n.

引用

页码：128 / 131

页数：3

共 10 条

[1]

Adleman L., Molecular computing of solution to combinatorial problems, Science, 266, pp. 1021-1024, (1994)

[2]

Kari L., DNA Computing-arrival of biological mathematics, The Mathematical Intelligence, 19, 2, pp. 9-22, (1997)

[3]

Adleman L., Computing with DNA, Scientific American, 279, pp. 34-40, (1998)

[4]

Guo M., Chang W.-L., Ho M., Lu J., Cao J., Is optimal solution of every NP-complete or NP-had problem determined from its characteristic for DNA-based computing, Biosystems, 80, 1, pp. 71-82, (2005)

[5]

Amos M., Paun G., Rozenberg G., Saloma A., Topic in the theory of DNA computing, Theoretical Computer Science, 287, pp. 3-38, (2002)

[6]

Braich R.S., Chelyapov N., Johnson C., Rothemund P.W.K., Adleman L., Solution of a 20-variable 3-SAT problem on a DNA computer, Science, 296, 5567, pp. 499-502, (2002)

[7]

Lipton R.J., DNA solution of hard computational problems, Science, 268, pp. 542-545, (1995)

[8]

Yang C.-N., Yang C.-B., A DNA solution of SAT problem by a modified sticker model, BioSystems, 81, 1, pp. 1-9, (2005)

[9]

Papadimitriou C.H., Steiglitz K., Combinatorial Optimization Algorithm and Complexity, (2003)

[10]

Chung W.Y., Chih P.C., Kee R.W., Molecular solution to the binary integer programming problem based DNA computing, BioSystems, 83, pp. 56-66, (2005)

← 1 →