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

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

關(guān)鍵詞：圖靈機(jī)；P類；NP類；NPC問題

中圖分類號：TP301.5

文獻(xiàn)標(biāo)志碼：A

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

0 引言

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

1 計算模型

1．1 圖靈機(jī)

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

1．2 圖靈機(jī)的變種

圖靈機(jī)有很多變種，如多帶圖靈機(jī)、非確定型圖靈機(jī)、交替式圖靈機(jī)和枚舉器等。其中多帶圖靈機(jī)與普通圖靈機(jī)相似，只是有多個存儲帶和讀寫頭，但其運(yùn)行的每一步也都是確定惟一的；而非確定型圖靈機(jī)(Non-Deterministic One-tape TuringMachine，簡稱NDTM)在計算過程中則可在多種可能性動作中選擇一種繼續(xù)進(jìn)行。……