QQ客服 官方微博 反馈留言

	The surface-based approach for DNA computation is unreliable for SAT
	Li, DF ; Li, XR ; Huang, HT ; Li, XX
	2010-05-06 ; 2010-05-06 ; OCT
关键词	DNA computing on surfaces satisfiability 3-SAT MOLECULAR COMPUTATION HAIRPIN FORMATION Biology
中文摘要	Previous research presented DNA computing on surfaces, which applied to each clause three operations: "mark", "destroy'; I and "unmark", and demonstrated how to solve a four-variable four-clause instance of the 3-SAT. It was claimed that only the strands satisfying the problem remained on the surface at the end of the computation and the surface-based approach was capable of scaling up to larger 3-SAT problems. Accordingly, the identities of the strands were only determined in the "readout 4 step for the correct solutions to the problem without checking if the strands really satisfied the problem. Thus, based on the claim above, the surface-based approach became a polynomial-time algorithm. In this paper, we show that for some instance of SAT, at the end of the computation all the remaining strands falsify the instance. However, by the previous claim all the strands falsifying the problems would be regarded as the correct solutions to the problems. Therefore, the DNA computing on surfaces is unreliable. For this reason, it is necessary to add a "verify" step after the "readout" step to check if the strands remaining on the surface at the end of the computation really satisfy the problem. (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/14099]
专题	清华大学
推荐引用方式 GB/T 7714	Li, DF,Li, XR,Huang, HT,et al. The surface-based approach for DNA computation is unreliable for SAT[J],2010, 2010, OCT.
APA	Li, DF,Li, XR,Huang, HT,&Li, XX.(2010).The surface-based approach for DNA computation is unreliable for SAT..
MLA	Li, DF,et al."The surface-based approach for DNA computation is unreliable for SAT".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

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