“至於你說得什麼np完全問題，那不就是以多項式時間作為上限，無限去做約化。我解不出一元一次的，我就去解更復雜的二元一次；解不出二元一次，就去解更復雜的三元一次。
這樣無限套娃下去，約化到一個無限複雜的問題，你拍著胸脯說：嘿，只要把這道題解出來，世界上所有問題就都難不倒我了！”
盧赫說完，右手搭在艾達否肩膀上，左手指著天空：“老艾啊，哥送你一句話：仰望星空，腳踏實地。左腳蹬右腳永遠都上不了天。”
艾達否聽後不屑地笑了笑，“你可去拉倒吧，你個思想落伍的保守分子。dna計算機是怎麼工作的你知道嗎？”
“怎麼工作的啊？”盧赫來了興致。
艾達否一臉認真地娓娓道來：
“你知道哈密頓問題嗎？圖論裡面的最著名難題。不知道也沒關係，給你簡單點描述一下：
假如你是一個時間管理大師，同時交往著5的女朋友，這些女朋友分佈在5個不同的城市。有一天，你被老闆派到另一個城市出差。好巧不巧，在那個城市你一個女朋友都沒有，而你非常想念她們，想借著公費出差的機會，把這5個女朋友都見一遍。
本小章還未完，請點選下一頁繼續閱讀後面精彩內容！
由於經費有限，你又很摳門不想多掏機票錢，所以每個城市只能去一次。同時這些城市之間又不全部都有雙向直飛航線，你該怎麼做呢？
你可以想想，但我告訴你不論你怎麼想都沒用。因為這類問題的解法只有一個，那就是試！和我們暴力破解密碼一樣，一個一個試！
進一步的，如果你不只五個女朋友，而是有50個、500個、5萬個、無窮個，你該怎麼辦？”
盧赫對著艾達否逐漸由認真轉為嬉笑的臉，思索片刻，答道：“我覺得這個問題我不需要考慮。5個女朋友大眼一瞅在紙上畫畫也就出來了，如果再多，我肯定會先死在床上。”
“你個死變態。”艾達否一臉嫌棄道：
“很難對吧？這其實是一個時間複雜度為n!的問題，也就是說，如果你有n個女朋友，就要嘗試n的階乘次。如果你女朋友多達萬個，就算是擁有4萬個核心天河三號，也要算到你年過花甲。
可這個問題對於dna計算機來說，卻是小菜一疊。它是這麼算的：
假如你現在剛見完1號女朋友，準備奔赴到2號的懷抱。那麼你離開1號女朋友的行為，就被編碼為acac；奔赴2號女朋友的行為，被編碼為gtgt。把這兩串編碼合起來，acacgtgt就代表你從1號到2號的路徑。
接下來，你見完了2號女朋友，又匆匆趕往3號。這個過程可以再用編碼表示為tctcagag。
也就是說，8個鹼基就可以用來表示你和其中一個女朋友從見面到拜拜的全過程。這個時候你肯定就要問了，我要你規劃一條連續的路徑，可acacgtgt、tctcagag是分離的兩條鏈，這還怎麼能玩兒的下去？
很簡單嘛，鹼基對是可以互補的。你再找一條cacaagag，不就可以跟膠水一樣，把那兩條毫不相關的鏈給粘起來了嗎？
接下來的事情就更簡單了。你有幾個女朋友，就用幾串8位編碼來表示和她們的見面和拜拜的過程。然後你把你的女朋友和膠水都合成一下，擴增個幾萬億條，放在一起，養蠱。
根據鹼基配對原則，膠水分分鐘就能發揮作用，把各種女朋友給粘起來。這個時候，你會得到幾萬億條路徑。這就是路徑遍歷的所有結果。
那你又要問，我怎麼把最省錢的那一條路徑給篩選出來呢？
這也很簡單，你的起點和終點是固定的。只要拿起點和終點作引物，擴增一下，起終點正確的路才能被擴增，不正確的會被逐漸稀釋掉。至於有些路徑上，你少見了幾個女朋友，或者重複多見了幾個女朋友，這些鏈的長度肯定是不對的。
最終，你把它們電泳一下，鏈長的和鏈短的分開，挑出長度剛好的鏈，測個序，答案不就出來了嗎？”
艾達否說完，搶過盧赫手裡的水，猛灌了幾口，“要知道，1克的dna可以儲存215pb的資料，相當於2億部小電影。這還不算完，由於鹼基配對的速度不慢，這215pb可以直接當作記憶體用，有幾條鏈就相當於有幾個執行緒並行執行。
有個神仙已經設計出了多項式時間的、基於dna演算法的np完全演算法，只不過減少時間複雜度的時候，犧牲掉了空間複雜度。這個演算法實現起來，需要有指數數量的編碼方式，和鉅額的儲存空間。
