Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/33346
Title: Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing
Authors: Guo, M
Chang, WL
Ho, M
Lu, J
Cao, J 
Keywords: Cook's Theorem
DNA-based computing
Molecular computing
NP-complete problems
NP-hard problems
Vertex-cover problem
Issue Date: 2005
Publisher: Elsevier
Source: BioSystems, 2005, v. 80, no. 1, p. 71-82 How to cite?
Journal: BioSystems 
Abstract: Cook's Theorem [Cormen, T.H., Leiserson, C.E., Rivest, R.L., 2001. Introduction to Algorithms, second ed., The MIT Press; Garey, M.R., Johnson, D.S., 1979. Computer and Intractability, Freeman, San Fransico, CA] is that if one algorithm for an NP-complete or an NP-hard problem will be developed, then other problems will be solved by means of reduction to that problem. Cook's Theorem has been demonstrated to be correct in a general digital electronic computer. In this paper, we first propose a DNA algorithm for solving the vertex-cover problem. Then, we demonstrate that if the size of a reduced NP-complete or NP-hard problem is equal to or less than that of the vertex-cover problem, then the proposed algorithm can be directly used for solving the reduced NP-complete or NP-hard problem and Cook's Theorem is correct on DNA-based computing. Otherwise, a new DNA algorithm for optimal solution of a reduced NP-complete problem or a reduced NP-hard problem should be developed from the characteristic of NP-complete problems or NP-hard problems.
URI: http://hdl.handle.net/10397/33346
ISSN: 0303-2647
EISSN: 1872-8324
DOI: 10.1016/j.biosystems.2004.10.003
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

36
Last Week
0
Last month
0
Citations as of Sep 19, 2017

WEB OF SCIENCETM
Citations

27
Last Week
0
Last month
0
Citations as of Sep 25, 2017

Page view(s)

40
Last Week
1
Last month
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.