首页 | 本学科首页   官方微博 | 高级检索  
     


Is DNA computing viable for 3-SAT problems?
Authors:Dafa Li
Affiliation:

Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Abstract:Adleman reported how to solve a 7-vertex instance of the Hamiltonian path problem by means of DNA manipulations. After that a major goal of subsequent research is how to use DNA manipulations to solve NP-hard problems, especially 3-SAT problems. Lipton proposed DNA experiments on test tubes to solve 3-SAT problems. Liu et al. reported how to solve a simple case of 3-SAT using DNA computing on surfaces. Lipton's model of DNA computing is simple and intuitive for 3-SAT problems. The separate (or extract) operation, which is a key manipulation of DNA computing, only extracts some of the required DNA strands and Lipton thinks that a typical percentage might be 90. But it is unknown what would happen due to imperfect extract operation. Let p be the rate, where 0<p<1. Assume that for each distinct string s in a test tube, there are 10l (l=13 proposed by Adleman) copies of s and that extracting each of the required DNA strands is equally likely. Here, the present paper will report, no matter how large l is and no matter how close to 1 p is, there always exists a class of 3-SAT problems such that DNA computing error must occur. Therefore, DNA computing is not viable for 3-SAT.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号