On the computational power of DNA

被引：82

作者：

Boneh, D ^{[1
]}

Dunworth, C ^{[1
]}

Lipton, RJ ^{[1
]}

Sgall, J ^{[1
]}

机构：

[1] AV CR,INST MATH,PRAGUE 11567 1,CZECH REPUBLIC

来源：

DISCRETE APPLIED MATHEMATICS | 1996年 / 71卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/S0166-218X(96)00058-3

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show how DNA-based computers can be used to solve the satisfiability problem for boolean circuits. Furthermore, we show how DNA computers can solve optimization problems directly without first solving several decision problems. Our methods also enable random sampling of satisfying assignments.

引用

页码：79 / 94

页数：16