QQ客服 官方微博 反馈留言

	Scalability of the surface-based DNA algorithm for 3-SAT
	Li, Dafa ; Li, Xiangrong ; Huang, Hongtao ; Li, Xinxin
	2010-05-06 ; 2010-05-06
关键词	DNA computing on surfaces satisfiability 3-SAT MOLECULAR COMPUTATION HAIRPIN FORMATION Biology
中文摘要	Since Adleman first proposed DNA computing for the Hamiltonian path problem, several authors have reported DNA computing for 3-SAT. Previous research presented DNA computing on surfaces and demonstrated how to solve a four-variable four-clause instance of 3-SAT, and claimed that the surface-based approach was designed to scale up to larger problems. In this paper we establish an error model for the incomplete "mark" and imperfect "destroy" operations. By using the error model we argue that no matter how large the "mark" and "destroy" rates are we can always give satisfiable instances of 3-SAT such that no DNA strands remain on the surface at the end of the computation. By the surface-based approach the satisfiable instances of 3-SAT would be misdetermined to be unsatisfiable. Thus, the error leads to an incorrect result of the SAT computation. Furthermore, given the "mark" rate p and the "not-destroy" rate p, we find that the approach can only solve at most N-variable instances of 3-SAT problems, where N = [(2 + beta(2) + 2 root 1+2 beta(2))/beta(2)] in which beta = 1 - 1 /(p + pq) and q = 1 - p and [a] is the greatest integer less than a or equal to a. (c) 2005 Elsevier Ireland Ltd. All rights reserved.
语种	英语 ; 英语
出版者	ELSEVIER SCI LTD ; OXFORD ; THE BOULEVARD, LANGFORD LANE, KIDLINGTON, OXFORD OX5 1GB, OXON, ENGLAND
内容类型	期刊论文
源URL	[http://hdl.handle.net/123456789/14025]
专题	清华大学
推荐引用方式 GB/T 7714	Li, Dafa,Li, Xiangrong,Huang, Hongtao,et al. Scalability of the surface-based DNA algorithm for 3-SAT[J],2010, 2010.
APA	Li, Dafa,Li, Xiangrong,Huang, Hongtao,&Li, Xinxin.(2010).Scalability of the surface-based DNA algorithm for 3-SAT..
MLA	Li, Dafa,et al."Scalability of the surface-based DNA algorithm for 3-SAT".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。