2 註解
1994年,美國加州大學的L. Adleman博士在《Science》上公佈了DNA計算機的理論,併成功地在DNA溶液的試管中進行了運算實驗。L. Adleman博士的DNA計算機完全是一種新的觀念。其基本設想是:以DNA鹼基序列作爲信息編碼的載體,利用現代分子生物學技術,在試管內控制酶作用下的DNA序列反應,作爲實現運算的過程;即以反應前的DNA序列作爲輸入的數據,反應後的DNA序列作爲運算的結果。DNA計算機是一種化學反應計算機。到目前爲止,已有人通過DNA計算機模型進行實驗解決了一些基本的NP問題。如L. Adleman博士做的對貨郎擔問題(哈密頓圖問題,HPP)的計算,和普林斯頓大學查科普頓作的可滿足性問題(SAT問題) 。所謂NP問題 ,是指人們根據問題類的算法複雜程度的劃分而言,與P問題相對。P問題是指算法複雜性隨着問題規模的增長而呈多項式增長的算法,是可以計算的。NP問題是指指算法複雜性隨着問題規模的增長而呈指數增長的算法,是實際上不可計算的。DNA計算機的構想是一種創新,具有巨大的潛力。DNA計算機運算速度快,其幾天的運算量就相當於計算機問世以來世界上所有計算機的運算總量。它的存儲容量非常巨大,而耗能卻只有一臺普通計算機的十億分子一。當然,DNA計算機畢竟只是一種理論設想,在很多方面還相當不完善。主要表現在:
1. 構造的現實性及計算潛力。DNA計算機以編碼後的DNA序列作爲輸入,在試管內反應完成計算,反應產物及溶液給出了全部解空間,但是最優解如何與其他解分離,怎樣輸出,是一個技術性極強的問題。目前還沒有令人滿意的輸出手段。隨着求解問題規模的擴大,輸出將成爲DNA計算機的瓶頸。
2. 運算過程中的錯誤問題。在擴增DNA的過程中,有較高的錯配率,而且大量的DNA在幾百步的反應中也會產生一些支路反應。錯誤會產生僞解,並增加最優解輸出的難度。