DNA计算机上一个20变量3-SAT问题的解决方案。
Solution of a 20-variable 3-SAT problem on a DNA computer.
作者信息
Braich Ravinderjit S, Chelyapov Nickolas, Johnson Cliff, Rothemund Paul W K, Adleman Leonard
机构信息
University of Southern California, Laboratory for Molecular Science, Los Angeles, CA 90089-1340, USA.
出版信息
Science. 2002 Apr 19;296(5567):499-502. doi: 10.1126/science.1069528. Epub 2002 Mar 14.
A 20-variable instance of the NP-complete three-satisfiability (3-SAT) problem was solved on a simple DNA computer. The unique answer was found after an exhaustive search of more than 1 million (2(20)) possibilities. This computational problem may be the largest yet solved by nonelectronic means. Problems of this size appear to be beyond the normal range of unaided human computation.
一个包含20个变量的NP完全三可满足性（3-SAT）问题在一台简单的DNA计算机上得到了解决。在对超过100万（2的20次方）种可能性进行穷举搜索后找到了唯一答案。这个计算问题可能是迄今为止通过非电子手段解决的最大的问题。这种规模的问题似乎超出了人类 unaided 计算的正常范围。
Zotero 插件