Molecular Computing
Molecular Computing
复制标题
分子计算
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Donald Beaver
中科院分区：
文献类型：
--
作者：
Donald Beaver
我们设计了一个分子图灵机，并确定了分子计算机可解决问题的复杂性。[94]中提出并实现了一种解决哈密顿路径np完全问题的组合分子实验。使用我们的设计，我们表明，在A94中隐含的慷慨假设下，这种分子计算机实际上可以计算PSPACE。在A94]无法满足的更强、更实际的限制条件下，我们证明了分子计算机仅限于解决P中的问题。
We design a molecular Turing machine and determine the complexity of the problems solvable by molecular computers. In A94], a combinatorial molecular experiment to solve the NP-complete problem of Hamiltonian Path was proposed and implemented. Using our design, we show that such molecular computers can in fact compute PSPACE, under the generous assumptions implicit in A94]. Under stronger and somewhat more practical restrictions, which A94] fails to satisfy, we show that molecular computers are limited to solving problems in P.