基于圖靈模型的P=?NP問題分析

摘要：P=?NP問題是計算復雜性中的核心問題。2000年，美國克雷實驗室將其收錄為“千禧年大獎”七個問題之首。本文基于圖靈模型，對P=?NP問題的研究現狀、P=NP／P≠NP證明方法、NPC問題求解方法及研究進展進行闡述。

關鍵詞：圖靈機；P類；NP類；NPC問題

中圖分類號：TP301.5

文獻標志碼：A

文章編號：1006-8228(2011112-01-02

0 引言

上世紀60年代中期，Hartmanis等人提出了按照對資源(時間、空間)需求的不同來劃分問題的方法，開創了計算復雜性理論。此后幾年，隨著研究的深入，越來越多的問題涌現出來，而經典的P=？NP問題則是計算復雜性中的核心問題。2000年，美國克雷實驗室將其收錄為“千禧年大獎”七個問題之首。本文基于圖靈模型，對P=?NP問題的研究現狀、P=NP／PNP證明方法、NPC問題求解方法及研究進展作一闡述。

1 計算模型

1．1 圖靈機

1936年，Alan Turing提出圖靈機計算模型，其基本思想是用機器來模擬人們用紙筆進行數學運算的過程。圖靈機也稱為確定型單帶圖靈機(Deterministic One-tape Turing Machine，簡稱DTM)，它用一個無限長的帶子作為無限存儲器，有一個讀寫頭能在有限狀態控制器控制下在帶子上讀、寫和左右移動，其運行的每一步都是確定惟一的。圖靈機運行時，機器預置了兩種狀態，如果進入這兩種狀態就產生輸出接受或拒絕，否則繼續執行下去，永不停止。

1．2 圖靈機的變種

圖靈機有很多變種，如多帶圖靈機、非確定型圖靈機、交替式圖靈機和枚舉器等。其中多帶圖靈機與普通圖靈機相似，只是有多個存儲帶和讀寫頭，但其運行的每一步也都是確定惟一的；而非確定型圖靈機(Non-Deterministic One-tape TuringMachine，簡稱NDTM)在計算過程中則可在多種可能性動作中選擇一種繼續進行。目前NDTM仍是一種假想的機器，但在NP問題研究中有重要作用。可以證明，這些圖靈機的變種的計算能力都是等價的，即它們能識別同樣的語言類。

定理1 設t(n)是一個函數，t(n)≥n。則每一個t(n)時間的多帶圖靈機都和某一個0(t2(n))時間的單帶圖靈機等價。

定理2 設t(n)是一個函數，t(n)≥n。則每一個t(n)時間的非確定型單帶圖靈機都與某一個2時間的確定性單帶圖靈機等價。

2 P問題和NP問題

圖靈論題將問題分為可計算的與不可計算的，只有能被圖靈機接受或拒絕的問題才認為是可計算問題，否則認為是不可計算問題。而計算復雜性理論又將可計算問題分為易解的和難解的。通常認為多項式時間內可解的問題為易解的，否則為難解的。

2．1 P類問題與NP類問題定義

P類問題即由確定型單帶圖靈機在多項式時間內可判定的問題。由定理1可知，確定型模型間存在多項式差異，由此可知所有確定型計算模型P是穩定的。

NP類問題即由非確定性圖靈機在多項式時間內可判定的問題。由于確定型圖靈機和非確定性圖靈機間存在指數級差異，通常認為NP問題為難解問題。也稱為多項式內可驗證的問題，因為驗證—個問題比判定一個問題容易得多。

由于確定型圖靈機是非確定型圖靈機的一種特例，所以P屬于NP，那么P=NP是否成立呢?

2．2 NPC類問題

1971年5月，加拿大多倫多大學教授斯蒂芬·庫克(Stephen Arthur Cook)在著名的論文《The Complexity ofTheorem Proving Procedures》中首次明確提出了NP完全性問題，奠定了NP完全性理論的基礎。NPC類是NP類的子類，是NP類中最難問題的集合，所有的NP問題都可以約化成它，由此推動了P=?NP問題的證明。

2．3 P=?NP研究意義

通過多年的探索，科學家們仍沒找出某個NPC問題的多項式算法，由此，人們開始相信P≠NP，但至今仍未有完備的理論證明。

早期人們一直相信質數證明問題是NP問題，在2002年，該問題被人解出是一個P類問題。因此，是否不能證明P=NP，只是因為我們至今未能找出多項式算法呢?若P≠NP，未來的研究將不會出現太大的變化，但如果P=NP那將意味著每一個多項式時間可驗證的問題都能找到有效時間解。隨著計算機在日常生活和各個科學研究領域的廣泛應用，人們越來越認識到許多問題的難解性，而P=NP命題的成立將徹底改變我們現在的生活，如天氣預報、圖像識別等人工智能問題都將得到解決，集裝箱、旅行商等日常問題也能有效解決，極端復雜的數學理論證明將找到更短的邏輯和更充分的證明，基于密鑰的安全系統將失靈，研究人員會將注意力轉向NP問題。

3 P=?NP證明方法

由于所有NP類問題在多項式內可約化為NPC問題，要證明P=NP，則需找到NPC類中某個特定問題是P類問題即可，即找出該問題的多項式算法，且要求算法的每一步在圖靈機模型上多項式時間內實現。

而要證明P≠NP，就須用數學理論證明這樣的算法是不存在的。人們已經做了很多嘗試，包括對角化、電路復雜性方法、復雜性證明方法、代數方法、有限模型理論方法等。下面列出幾個方法加以闡述：

(1)對角化方法。早在1874年，數學家Georg Cantor就提出了對角化方法，而后Alan Turing將此方法用于停機問題不可計算的證明。上世紀六十年代，復雜性理論研究人員又將此方法用于證明更多的時間和空間能求解更大的問題，由此，人們開始考慮將該方法用于P=?NP問題的證明。對角化方法的核心是一臺圖靈機對另一臺圖靈機的模擬，即模擬機器能夠確定另一臺機器的行為，從而以不同方式動作。由此，能否構造一個特定的的NP類語言L，致使每個單一的多項式算法都無法在某些輸入下正確計算出L，即證明如何用一個確定的NP機器模擬任意的P機器。對角化方法已證明許多NP完全問題不可能有少量時間和空間可解的算法，但離解決P≠NP問題還有很遠的距離。

(2)電路復雜性方法。該方法通過電路的并行性，用與、或和非三個基本門和導線構造的無環圖電路模型(即布爾電路)來模擬圖靈機模型處理P與NP問題及相關問題，證明P≠NP，即NP完全問題無法通過邏輯門的數量為多項式規模的電路來解決。目前，Savage證明了電路規模與圖靈機時間之間有一個緊密的關系，如定理3，并對COOK定理的證明提出了另一種方法，為P=?NP問題的證明給出新的思路。

定理3 設t：N—N是一個函數，t(n)≥n。若A∈TIME(t(n))，則A的電路復雜度為0(t2(n))。

Razborov和Rudich提出了一種電路下限的“自然證明法”證明電路復雜性問題，而后發現自身矛盾，證明電路復雜性方法不太可能成功解決P=?NP問題。

(3)復雜性證明方法。重言式是一個真值為O或l的一組變量由與、或、非相連的布爾表達式，并且無論變量如何取值都能使得表達式的值為真。證明P≠NP問題則意味著證明重言式不存在短證明(即有界的多項式證明)。

消解法是證明重言式的一種標準方法，其出發點是，一個式子是個重言式當且僅當能產生一個空子句。1985年，Armin Haken提出編碼鴿籠問題的重言式沒有短證明方法，但這不能說明任意一個重言式都不存在短證明，因此離P=?NP問題的證明還存在一定距離。

4 NPC問題求解

由于研究人員至今仍未發現NPC問題的多項式求解方法，而現實生活中又有大量NPC問題需要求解，因此如何找到這樣一些難解的NPC問題求解方法一直是研究的熱點。

蠻力搜索方法的做法是遍歷問題的各種可能解，從而找出最優解。該算法在求解NPC問題時，由于問題本身的難解性而耗費無法接受的時間量。但隨著計算機硬件的飛速發展，蠻力搜索法能求解問題的規模逐步增大，如TSP問題已找出遍歷10000個城市的最優路徑。但在大規模問題求解及算法效率上還存在很大不足。

目前，利用近似算法和概率算法求解難解問題成為NPC問題求解的主要方法。在實際中，對于復雜問題找到問題最優解較為困難，并且用戶也并非要求得問題的絕對最優。近似算法就是為尋求問題的近似最優解而設置的。如旅行商問題中通過構造一個頂點集的歐拉回路來尋求近似回路求解問題、貪心算法求解裝箱問題等；而概率算法在求解問題時下一步操作都是不確定的，它通過隨機選擇下一個計算步驟來降低算法復雜度，最終求得問題近似解近似解的精度隨計算時間的增加不斷提高。著名的蒙特開羅算法、拉斯維加斯算法和舍伍德算法已在實際問題的求解中得到廣泛應用。

5 研究進展

2007年，D-Wave公司聲稱制造出了有16個qubit的絕熱量子計算機，通過讓計算機的溫度維持在絕對零度左右，減少對量子效應的干涉，使量子計算機能正常工作。量子計算機本質上是基于態疊加原理的天生的并行計算機。它的提出給P=?NP問題的研究帶來新的希望。

2010年，美國HP研究院的Vinay Deolalikar在8月8號發布一篇希望能證明P!=NP的論文，他將有限模型理論和Random SAT模型串聯起來證明該問題。總體來說，這種證明思路還是比較新穎，但在其證明過程上還存在很大異議。

6 結束語

P=?NP已經從一個令人感興趣的數學問題發展到21世紀成為最基本、最重要的數學問題，而且它的重要性還將隨著計算機技術的進展和普及而增長，它對許多領域的理論研究和實際問題的求解產生了深遠的影響。