Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing

Minyi Guo, Weng Long Chang, Machael Ho, Jian Lu, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

44 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)71-82
Number of pages12
JournalBioSystems
Volume80
Issue number1
DOIs
Publication statusPublished - 1 Jan 2005

Keywords

  • Cook's Theorem
  • DNA-based computing
  • Molecular computing
  • NP-complete problems
  • NP-hard problems
  • Vertex-cover problem

ASJC Scopus subject areas

  • Statistics and Probability
  • Modelling and Simulation
  • Biochemistry, Genetics and Molecular Biology(all)
  • Applied Mathematics

Cite this