Abstract | ||
---|---|---|
: We show how to extend the recent result of Adleman [1] to use biologicalexperiments to directly solve any NP problem. We, then, show how to use this methodto speedup a large class of important problems.1. IntroductionIn a recent breakthrough Adleman [1] showed how to use biological experiments to solveinstances of the famous Hamiltonian Path Problem (HPP). Since this problem is knownto be NP-complete it follows that biology can be used to solve any problem from NP.Recall that all... |
Year | Venue | Keywords |
---|---|---|
1995 | DNA Based Computers | hamiltonian path problem,molecular biology |
Field | DocType | Citations |
Computer science,Computational biology,Computation | Conference | 21 |
PageRank | References | Authors |
32.92 | 0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Richard J. Lipton | 1 | 6412 | 1796.57 |