DNA SOLUTION OF HARD COMPUTATIONAL PROBLEMS
DNA SOLUTION OF HARD COMPUTATIONAL PROBLEMS
复制标题
DOI：
10.1126/science.7725098
复制
发表时间：
1995-04-28
期刊：
影响因子：
56.9
通讯作者：
LIPTON, RJ
中科院分区：
文献类型：
--
作者：
LIPTON, RJ
有人提出用DNA实验来解决计算机科学中著名的“可满足性”（SAT）问题。这是一种能够解决NP完全问题的更通用方法的一个特例。这些成果的优势在于基于DNA的计算所固有的巨大并行性。对于此类搜索问题，它有可能比传统的基于电子的计算机大幅提高速度。
DNA experiments are proposed to solve the famous ''SAT'' problem of computer science. This is a special case of a more general method that can solve NP-complete problems. The advantage of these results is the huge parallelism inherent in DNA-based computing. It has the potential to yield vast speedups over conventional electronic-based computers for such search problems.