Li Dafa, Li Xiangrong, Huang Hongtao, Li Xinxin
Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China.
Biosystems. 2005 Oct;82(1):20-5. doi: 10.1016/j.biosystems.2005.05.007.
Previous research presented DNA computing on surfaces, which applied to each clause three operations:"mark","destroy", and "unmark", and demonstrated how to solve a four-variable four-clause instance of the 3-SAT. It was claimed that only the strands satisfying the problem remained on the surface at the end of the computation and the surface-based approach was capable of scaling up to larger 3-SAT problems. Accordingly, the identities of the strands were only determined in the"readout" step for the correct solutions to the problem without checking if the strands really satisfied the problem. Thus, based on the claim above, the surface-based approach became a polynomial-time algorithm. In this paper, we show that for some instance of SAT, at the end of the computation all the remaining strands falsify the instance. However, by the previous claim all the strands falsifying the problems would be regarded as the correct solutions to the problems. Therefore, the DNA computing on surfaces is unreliable. For this reason, it is necessary to add a "verify" step after the "readout" step to check if the strands remaining on the surface at the end of the computation really satisfy the problem.
先前的研究提出了表面上的DNA计算，该计算对每个子句应用三种操作：“标记”、“销毁”和“取消标记”，并演示了如何解决3-SAT的一个四变量四子句实例。据称，在计算结束时，只有满足问题的链留在表面上，并且基于表面的方法能够扩展到更大的3-SAT问题。因此，链的身份仅在“读出”步骤中确定问题的正确解，而不检查链是否真的满足问题。因此，基于上述说法，基于表面的方法成为了一种多项式时间算法。在本文中，我们表明，对于某些SAT实例，在计算结束时，所有剩余的链都使该实例不成立。然而，根据先前的说法，所有使问题不成立的链都将被视为问题的正确解。因此，表面上的DNA计算是不可靠的。因此，有必要在“读出”步骤之后添加一个“验证”步骤，以检查在计算结束时留在表面上的链是否真的满足问题。
