NP 完全問(wèn)題研究及前景剖析

杜立智，陳和平，符海東

武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430065

0 引 言

對(duì)P和NP問(wèn)題的研究，關(guān)鍵有兩個(gè)方面，第一是對(duì)相關(guān)概念的正確理解和把握，第二是正確的研究方向與正確的研究方式方法.對(duì)于第一點(diǎn)，由于相關(guān)概念相當(dāng)復(fù)雜抽象，存在著許多理解上的謬誤.甚至一些翻譯過(guò)來(lái)的教科書(shū)都存在這些謬誤，從而影響了該專業(yè)的學(xué)生正確理解掌握相關(guān)概念.對(duì)于第二點(diǎn)，關(guān)鍵是傾向于以NP等于P為出發(fā)點(diǎn)還是相反.不同的出發(fā)點(diǎn)，對(duì)研究的成功與否，起著至關(guān)重要的作用.

而在所有NP相關(guān)問(wèn)題中，NP完全無(wú)疑是最重要的概念.事實(shí)上，對(duì)NP完全及其相關(guān)概念的透徹理解，是深入研究NP問(wèn)題，尤其是研究NP與P的關(guān)系問(wèn)題的關(guān)鍵.談到NP完全，又不能不涉及到多項(xiàng)式歸約.

本文的目的是，通過(guò)分析與NP問(wèn)題相關(guān)的核心概念，并通過(guò)對(duì)抽象定義的解析結(jié)合對(duì)認(rèn)識(shí)謬誤的剖析，揭示其實(shí)質(zhì).本文的關(guān)鍵點(diǎn)是，深入剖析NP完全問(wèn)題時(shí)間復(fù)雜度的邏輯內(nèi)涵，同時(shí)通過(guò)對(duì)多個(gè)實(shí)際問(wèn)題的分析，給出解決NP完全問(wèn)題的啟發(fā)式思路，從而為該領(lǐng)域的研究者在概念和研究方向的正確把握上提供參考.

1 NP和NP完全問(wèn)題的起源與基本思想及其影響和發(fā)展

NP問(wèn)題是隨著計(jì)算復(fù)雜性理論的產(chǎn)生而出現(xiàn)的.根據(jù)計(jì)算復(fù)雜性理論，所有科學(xué)問(wèn)題按其解決時(shí)間可分為三大類：多項(xiàng)式類、指數(shù)類和不可解類.但要確定某個(gè)具體的問(wèn)題到底屬于哪一類，往往并非一件容易的事情，尤其是對(duì)少數(shù)難度大的問(wèn)題［1－2］.

在理論計(jì)算機(jī)領(lǐng)域，對(duì)這三類問(wèn)題的研究本來(lái)就浩瀚和深不可測(cè)，隨著NP問(wèn)題的出現(xiàn)，事情就更復(fù)雜了.NP問(wèn)題是與確定性圖靈機(jī)和非確定性圖靈機(jī)的概念一起出現(xiàn)的［3］.這兩個(gè)概念相當(dāng)抽象，極難透徹理解掌握，從而更加為NP問(wèn)題蒙上了一層神秘色彩.

通俗地講，NP問(wèn)題是“多項(xiàng)式驗(yàn)證”問(wèn)題.也就是說(shuō)，若是有了某個(gè)NP問(wèn)題的解，要判斷這個(gè)解是否正確，這個(gè)判斷可以在多項(xiàng)式時(shí)間內(nèi)完成.至于求解這個(gè)問(wèn)題到底需要多少時(shí)間，先撇開(kāi).

自從NP問(wèn)題出現(xiàn)以后，學(xué)術(shù)界長(zhǎng)時(shí)間對(duì)此進(jìn)行了大量的投入及研究，盡管取得了不少研究成果，由于NP問(wèn)題的難度和深度，迄今為止，依然不能確定NP到底屬于上述三類問(wèn)題中的哪一類.可以確定兩點(diǎn)，其一是NP問(wèn)題空間復(fù)雜度是多項(xiàng)式，其二是，NP問(wèn)題時(shí)間復(fù)雜度的上限是指數(shù)型.所以，任何NP問(wèn)題要么是多項(xiàng)式，要么是指數(shù)型［4］，而不可能是不可解的問(wèn)題.不過(guò)，要確定NP到底是不是屬于多項(xiàng)式，確定這一點(diǎn)本身倒可能是不可解問(wèn)題.不少專家提出了這樣的判斷和疑問(wèn).

1937年，英國(guó)計(jì)算機(jī)科學(xué)家，同時(shí)也是計(jì)算復(fù)雜性理論開(kāi)山鼻祖的圖靈提出了一種自動(dòng)機(jī)模型，后來(lái)被人們稱作圖靈機(jī)，并論證了圖靈機(jī)的可計(jì)算功能.圖靈機(jī)模型的提出不僅為現(xiàn)代計(jì)算機(jī)的設(shè)計(jì)奠定了理論基礎(chǔ)，同時(shí)也成為引出和研究NP問(wèn)題的工具.

后進(jìn)一步分為確定性圖靈機(jī)（DTM）和非確定性圖靈機(jī)（NDTM）兩類.這兩個(gè)概念在教科書(shū)中的定義高度抽象，難以把握.筆者在這里用通俗的語(yǔ)言加以剖析.確定性圖靈機(jī)是現(xiàn)代計(jì)算機(jī)的理論模型，可以認(rèn)為現(xiàn)代計(jì)算機(jī)是對(duì)圖靈機(jī)理論模型的實(shí)現(xiàn).其計(jì)算功能與現(xiàn)代計(jì)算機(jī)等價(jià)，但還是有根本的不同，前者更抽象.筆者曾經(jīng)用確定性圖靈機(jī)進(jìn)行了編程練習(xí)，解決同樣的問(wèn)題，比當(dāng)今流行的計(jì)算機(jī)語(yǔ)言編程要難得多.而非確定性圖靈機(jī)則純屬理想的理論模型，現(xiàn)實(shí)中無(wú)法實(shí)現(xiàn).P類問(wèn)題也定義為在確定性圖靈機(jī)上能在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題；NP類問(wèn)題則是在非確定性圖靈機(jī)上能在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題.

非確定性圖靈機(jī)的最大特點(diǎn)就是具有并行運(yùn)算能力.但請(qǐng)注意正確理解它的關(guān)鍵是，這個(gè)并行并不是無(wú)限制的.它只能進(jìn)行“分叉”式的并行，而不能按許多甚至無(wú)數(shù)平行線 “平行”方式地并行.若是后者，那非確定性圖靈機(jī)就不僅能解決NP問(wèn)題，指數(shù)型問(wèn)題也能一塊解決了.用一顆n層的k叉樹(shù)來(lái)描述確定性非確定性圖靈機(jī)的區(qū)別無(wú)疑能說(shuō)明問(wèn)題，可以肯定所有NP問(wèn)題都可以翻譯成這個(gè)模型.對(duì)于這樣一棵樹(shù)，其節(jié)點(diǎn)數(shù)目是指數(shù)型，k的n次方.當(dāng)然這些節(jié)點(diǎn)之間有統(tǒng)一的聯(lián)系規(guī)律，這個(gè)規(guī)律信息是多項(xiàng)式.要尋找其中一個(gè)點(diǎn)，以及從頂點(diǎn)到這個(gè)點(diǎn)的一條路徑，非確定圖靈機(jī)從頂點(diǎn)開(kāi)始向下，在每一個(gè)分叉處能并行地同時(shí)向所有分支走下去，從而，最多n步就能達(dá)到目的；而確定性圖靈機(jī)無(wú)并行能力，它需要遍歷整個(gè)樹(shù)，才能保證找到目標(biāo).當(dāng)然，也不排除有高超的算法使其能快速得到結(jié)果.

顯而易見(jiàn)，所有多項(xiàng)式問(wèn)題，也就是P類問(wèn)題，肯定屬于NP.因?yàn)槟茉诙囗?xiàng)式時(shí)間內(nèi)計(jì)算出結(jié)果的，必然也能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證結(jié)果.但NP是否屬于P成了該領(lǐng)域的最大難題，迄今無(wú)法確定.該問(wèn)題的解決不僅能在該領(lǐng)域帶來(lái)理論上的重大突破，并且也能對(duì)許多重要的問(wèn)題的實(shí)際計(jì)算具有意義.

1971年，NP問(wèn)題的研究取得了里程碑的突破.加拿大著名計(jì)算機(jī)科學(xué)家史蒂文－庫(kù)克證明了存在具有NP完全性質(zhì)的NP問(wèn)題［5］，這就是可滿足性問(wèn)題（SAT），它也是人類發(fā)現(xiàn)的首個(gè)NP完全問(wèn)題（NPC）.所謂某問(wèn)題具備NP完全性，也就是，任何NP問(wèn)題的求解都可以多項(xiàng)式轉(zhuǎn)化到對(duì)該問(wèn)題的求解.庫(kù)克構(gòu)造了一般NP問(wèn)題，也就是任意NP問(wèn)題多項(xiàng)式轉(zhuǎn)化為SAT問(wèn)題的轉(zhuǎn)化方法和公式，從而完成了NP完全的證明.其邏輯結(jié)果是：如果能得到可滿足性問(wèn)題的多項(xiàng)式時(shí)間算法，那就意味著所有NP問(wèn)題都具有多項(xiàng)式時(shí)間算法，即NP等于P.請(qǐng)注意證明某NP問(wèn)題具有NP完全性，通常是一道艱難的工作，普通的NP問(wèn)題并不具備這一特性.而大量的NP問(wèn)題其實(shí)就是非常簡(jiǎn)明的P問(wèn)題.不少論文書(shū)刊中，經(jīng)常使用這樣的說(shuō)法：某問(wèn)題是NP，故無(wú)有效算法.這當(dāng)然是一種謬誤，是混淆了NP與NP完全的概念.

NP和NP完全問(wèn)題的出現(xiàn)，對(duì)計(jì)算機(jī)算法和計(jì)算復(fù)雜性領(lǐng)域，產(chǎn)生了重大而深遠(yuǎn)的影響.

隨著第一個(gè)NP完全問(wèn)題的發(fā)現(xiàn)和證明，興起了對(duì)這類問(wèn)題之間的多項(xiàng)式轉(zhuǎn)化研究.在教科書(shū)中通常將這種轉(zhuǎn)化稱為“歸約”［6］.注意理解多項(xiàng)式歸約必須把握兩個(gè)關(guān)鍵點(diǎn)：一是轉(zhuǎn)化本身所需的時(shí)間是多項(xiàng)式，二是轉(zhuǎn)化后對(duì)原問(wèn)題計(jì)算規(guī)模的擴(kuò)大，不超出多項(xiàng)式的范圍.例如，若需要將具有n個(gè)變量的3SAT問(wèn)題按多項(xiàng)式規(guī)約轉(zhuǎn)化為對(duì)另一NP問(wèn)題的求解，那么，轉(zhuǎn)化所需的時(shí)間不能超出n的多項(xiàng)式函數(shù)，同時(shí)，設(shè)轉(zhuǎn)化后后一問(wèn)題的大小規(guī)模為m，m也不能超出n的多項(xiàng)式函數(shù).若是m在n的基礎(chǔ)上呈指數(shù)型放大，即使轉(zhuǎn)化本身所花的時(shí)間很快，那當(dāng)然也不能稱作多項(xiàng)式歸約.

長(zhǎng)期以來(lái)，多項(xiàng)式轉(zhuǎn)化的研究一直經(jīng)久不衰.它主要有兩個(gè)方面的價(jià)值.從70年代初開(kāi)始，前期的研究主要是為了發(fā)現(xiàn)NP完全問(wèn)題.那時(shí)候每發(fā)現(xiàn)一個(gè)NP完全問(wèn)題，就是一個(gè)較轟動(dòng)的大成果.如今這個(gè)已經(jīng)不那么重要了.但由于NP完全問(wèn)題之間的多項(xiàng)式轉(zhuǎn)化性質(zhì)，若得到了一個(gè)問(wèn)題的高效算法，則可以通過(guò)轉(zhuǎn)化得到其他問(wèn)題的高效算法.因而前一類目的的研究已經(jīng)顯著降溫，后一類目的的研究則更有實(shí)用價(jià)值.

這就是NP完全問(wèn)題的意義和實(shí)質(zhì).

關(guān)于NP完全問(wèn)題，還有一個(gè)重要概念就是偽多項(xiàng)式時(shí)間算法.舉例來(lái)講，整數(shù)背包問(wèn)題：給定一些整數(shù) Cj， j＝1，2，…n，以及整數(shù) b，是否存在整數(shù) X1， …Xn＞＝0 使得該問(wèn)題是經(jīng)典的NP完全問(wèn)題，但該問(wèn)題存在針對(duì)參數(shù)n和b的多項(xiàng)式時(shí)間算法，稱偽多項(xiàng)式時(shí)間算法.也就是說(shuō)，必須限定b的大小為n的多項(xiàng)式，該問(wèn)題才具有多項(xiàng)式時(shí)間算法.而當(dāng)b很大，為n的指數(shù)冪時(shí)，按同樣方法得到的算法的時(shí)間復(fù)雜度就不是多項(xiàng)式，而是指數(shù)型了.一些研究者不理解這一點(diǎn)，花了大量的時(shí)間和精力，找到了該問(wèn)題的在限定了b的大小的前提下的多項(xiàng)式時(shí)間算法，就真的以為已經(jīng)解決了NP是否等于P的問(wèn)題.其實(shí)是大謬誤.

2 關(guān)于NP完全問(wèn)題時(shí)間復(fù)雜度的爭(zhēng)論

首先討論NP完全問(wèn)題時(shí)間復(fù)雜度的一些特點(diǎn).一般來(lái)說(shuō)，對(duì)于所熟悉的許多多項(xiàng)式時(shí)間問(wèn)題，其時(shí)間復(fù)雜度的曲線很光滑.也就是說(shuō)，局部范圍的輸入數(shù)據(jù)，往往具有整體時(shí)間復(fù)雜度的特性.例如，對(duì)于著名的冒泡排序算法，其時(shí)間復(fù)雜度在最壞的情況下是n的平方，在最快的情況下為常數(shù)，平均時(shí)間為二分之n的平方，且其分布呈光滑的曲線，并且這樣的曲線很容易通過(guò)算例描繪出來(lái).在n等于任何值的時(shí)候，都具有這樣的特點(diǎn).

NP完全問(wèn)題，比如哈密爾頓環(huán)，就完全不是這樣了.哈密爾頓環(huán)的特點(diǎn)是：對(duì)一個(gè)不大的n，其可能的算例數(shù)量極其龐大，且這些算例的難易程度分布相當(dāng)復(fù)雜，沒(méi)有規(guī)律，現(xiàn)在還沒(méi)有人能掌握這些算例難易程度的分布規(guī)律.例如，國(guó)際某網(wǎng)站有關(guān)于最難算的哈密爾頓的算例，這些算例用筆者的程序可以非常輕松和快速地解決.因而，對(duì)于某個(gè)NP完全問(wèn)題，一個(gè)計(jì)算程序所說(shuō)在最壞情況下的計(jì)算時(shí)間，只能指的是在所算的例子中最慢的那一個(gè)，而不是指：該程序找到了這樣的例子，它代表了此問(wèn)題計(jì)算時(shí)間復(fù)雜度的上限.這樣的例子是沒(méi)有人能找得到的，而冒泡排序之類的多項(xiàng)式問(wèn)題則非常容易找到這樣的例子，且呈固定的概率分布.

故而對(duì)NP完全問(wèn)題算法的思維不能停留在對(duì)一些簡(jiǎn)單問(wèn)題的思維層面上.就算真的能找到在最壞情況下的問(wèn)題，也不能排除在客觀世界存在有這樣的NP完全問(wèn)題，比如：它的時(shí)間復(fù)雜度上限是某個(gè)值，但在某個(gè)數(shù)據(jù)段，最壞的情況的復(fù)雜度是另一個(gè)值，在另一個(gè)數(shù)據(jù)段最壞的情況又是一個(gè)不同的值，等等.這就是為什么NP完全問(wèn)題時(shí)間復(fù)雜度難以確定的根本原因.

自從史蒂文庫(kù)克論證了NP完全問(wèn)題的存在，NP是否等于P隨即開(kāi)始困擾人類，考量著人類復(fù)雜的思路能力和計(jì)算能力.此問(wèn)題也很快被公認(rèn)為最具挑戰(zhàn)性的世界難題.如果能證明某個(gè)NP完全問(wèn)題存在多項(xiàng)式時(shí)間算法，即可判定所有NP問(wèn)題都具有多項(xiàng)式時(shí)間算法.如前所述，迄今已發(fā)現(xiàn)4千多個(gè)NP完全問(wèn)題，還沒(méi)有人能論證完全問(wèn)題學(xué)者具有多項(xiàng)式時(shí)間算法，也沒(méi)有人能否定其具有多項(xiàng)式時(shí)間算法.相關(guān)領(lǐng)域的學(xué)者往往根據(jù)自己的感覺(jué)或傾向擁有自己的判斷，這些判斷不能說(shuō)是科學(xué)的或有實(shí)際價(jià)值的.

有人對(duì)一些數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家做過(guò)統(tǒng)計(jì)，結(jié)果大多數(shù)傾向于認(rèn)為NP不等于P，只有小部分認(rèn)為兩者相等.

一些科學(xué)家在提出NP不等于P的判斷時(shí)，所舉的理由僅僅是泛泛的，而不具備嚴(yán)格的科學(xué)認(rèn)證價(jià)值.舉例如下：

一個(gè)算法學(xué)家，在一本算法專著上寫(xiě)到：迄今已出現(xiàn)了大量NP完全問(wèn)題，由于許多最優(yōu)秀的算法專家和數(shù)學(xué)家在長(zhǎng)期研究這些問(wèn)題，卻沒(méi)有找到一個(gè)多項(xiàng)式算法，故傾向于判斷NP不等于P［1］.

ACM期刊主編是這樣論證NP不等于P的：若誰(shuí)證明了NP等于P，則他不僅只是解決了NP問(wèn)題，所有7大世紀(jì)難題他都解決了，因?yàn)樗锌茖W(xué)研究問(wèn)題的解決都屬 NP［7］.

還有專家認(rèn)為：由于非確定性圖靈機(jī)的計(jì)算能力明顯強(qiáng)于確定性圖靈機(jī)，從而NP不等于P.當(dāng)然，也有不少專家認(rèn)為NP等于P.

下面給出NP是否等于P的一些啟發(fā)式思考.

3 科研問(wèn)題的解決與NP完全問(wèn)題

NP問(wèn)題為何如此具有影響力？其原因一是問(wèn)題本身確實(shí)難解，極具挑戰(zhàn)性，二是，它考量人類思維能力和計(jì)算能力的極限.人的思維是串行的而不具備并行思維能力，而所有科學(xué)問(wèn)題的解決途徑，其實(shí)都是NP.

若是NP等于P，則理論上，只具有串行思維能力的人類，可以解決所有科學(xué)難題.而若是NP不等于P，也就是大量的NP問(wèn)題會(huì)是指數(shù)型的，則不幸得很，大量科學(xué)問(wèn)題人類思維很難解決.因?yàn)橹笖?shù)型通常意味著2的n次方或更大，當(dāng)n的規(guī)模達(dá)到小小的100時(shí)，解決問(wèn)題所需的思維步驟將達(dá)100萬(wàn)億億億步，這是人類思維能力所無(wú)法企及的，哪怕花上萬(wàn)萬(wàn)年的時(shí)間.

從哲學(xué)上可以這么說(shuō)，是否贊成NP等于P，是區(qū)分可知論和不可知論的分水嶺.

公認(rèn)為20世紀(jì)最偉大的數(shù)學(xué)家的希爾伯特有句名言：我們必須知道，我們必能知道！可見(jiàn)，本質(zhì)上，希爾伯特是贊成NP等于P的！

而他在20世紀(jì)剛開(kāi)始所提出的23個(gè)高不可攀的數(shù)學(xué)問(wèn)題，也已經(jīng)陸續(xù)得到了解決，仿佛是在證明他的“我們必能知道”的斷言.

人類歷史上，一個(gè)個(gè)科學(xué)難題在不斷被解決，難道不是在印證著NP等于P嗎？

筆者對(duì)此的質(zhì)疑邏輯是：如前所述，所有科研難題的解決途徑是NP，因而NP是否等于P這一難題的解決途徑無(wú)疑也屬NP.鑒于這是科學(xué)難題，許多科學(xué)家判斷，該問(wèn)題人類長(zhǎng)時(shí)期很難解決，例如上述ACM的期刊主編就是這樣判斷的，因而有理由認(rèn)為該問(wèn)題屬于NP難，并且其解決過(guò)程所包含的參量也就是n不可能很小.

這意味著任何宣稱證明了NP不等于P的人，其實(shí)是在用自己證明的結(jié)論，去否決自己證明的可能性和正確性，也就是說(shuō)，是在循環(huán)否定.

4 圍棋軟件開(kāi)發(fā)與NP完全問(wèn)題

曾有人提議，若能開(kāi)發(fā)一個(gè)圍棋軟件，能打敗所有圍棋高手，也就是說(shuō)其思路已達(dá)到最優(yōu)，那不就一切都證明了嗎？此提議非常好，但要做好還有諸多困難，而且就算做好了，也不意味NP問(wèn)題的解決.

下圍棋屬敵對(duì)搜索，是極大極小搜索加剪枝問(wèn)題中的一種.問(wèn)題在于，它的分支數(shù)非常大，也就是可選的點(diǎn)很多，因而計(jì)算深度就只能很淺了，否則計(jì)算量和儲(chǔ)存量都會(huì)大得驚人.不僅如此，它的狀態(tài)值量化非常困難，從而在進(jìn)行優(yōu)劣選擇以及剪枝時(shí)，非常難以把握.因此，迄今最好的圍棋軟件只能達(dá)到業(yè)余二段的水平，與專業(yè)高段棋手比當(dāng)然是相差甚遠(yuǎn).

人下圍棋能達(dá)到專業(yè)強(qiáng)九段的水平，不妨假定此水平極高.由此就產(chǎn)生了如下問(wèn)題：（1）圍棋是NP嗎？（2）圍棋是NPC嗎？（3）此問(wèn)題能在多項(xiàng)式內(nèi)解決嗎？

注意到強(qiáng)九段，顯然，不能認(rèn)為強(qiáng)九段的思維能力和記憶能力能滿足指數(shù)型.不妨設(shè)想人類能出現(xiàn)這樣頂級(jí)的圍棋高手，他下棋就能達(dá)到最優(yōu)，也就是說(shuō)能在多項(xiàng)式時(shí)間內(nèi)完成判斷計(jì)算.這就意味著，一個(gè)明顯的指數(shù)型搜索問(wèn)題，有人卻可在多項(xiàng)式內(nèi)完成.這是如何辦到的呢？回答只能是：在充分研究后，加上充分的知識(shí)積累以及復(fù)雜的關(guān)聯(lián)信息的充分把握.從邏輯上可以判斷，人能做到的，軟件也應(yīng)能做到，且不會(huì)增加計(jì)算量和儲(chǔ)存量.

對(duì)這個(gè)問(wèn)題的分析，可以得到解決NP完全問(wèn)題的某些啟發(fā).

此外，近年來(lái)一些論文提到的一些研究技巧，亦對(duì) NP 問(wèn)題的研究有所助益［8－10］.

針對(duì)Hamilton環(huán)這一NP完全問(wèn)題的多項(xiàng)式時(shí)間算法的研究嘗試也一直在進(jìn)行［11］.多年來(lái)，筆者也堅(jiān)持進(jìn)行該問(wèn)題的研究，已經(jīng)有相當(dāng)樂(lè)觀的結(jié)果.

5 個(gè)體和群體及概率與NP完全問(wèn)題

同樣，從啟發(fā)思維的角度，如前所述，至今已發(fā)現(xiàn)了4 000多個(gè)NP完全問(wèn)題，且還會(huì)繼續(xù)發(fā)現(xiàn).由于任何一個(gè)NP完全問(wèn)題，都可以多項(xiàng)式規(guī)約到另一個(gè)任意的NP完全問(wèn)題，也就是說(shuō)，所有NP完全問(wèn)題兩兩之間的距離是多項(xiàng)式，這件事實(shí)本身強(qiáng)烈地昭示著（strongly imply），NP問(wèn)題具有統(tǒng)一的求解規(guī)律和難解度，并且也應(yīng)具有多項(xiàng)式量級(jí).

客觀世界的任何一個(gè)群體，其任意個(gè)體之間某個(gè)屬性的差值，與個(gè)體屬性的絕對(duì)值通常都處在同一個(gè)量級(jí).舉例說(shuō)來(lái)：通常成人的體重是百斤量級(jí)，很肥壯和很瘦的人之間體重的差值也是百斤量級(jí).同樣，很肥大的螞蟻與很瘦小的螞蟻體重之差值也與通常單個(gè)成年螞蟻的體重處在同一個(gè)數(shù)量級(jí).

再舉一個(gè)例子：假使在某個(gè)太空中隨機(jī)選n個(gè)點(diǎn)，n顯著大于1，若其中任兩個(gè)點(diǎn)之間的距離都不超過(guò)1010米，就有理由認(rèn)為，該太空本身的最大尺度也在1010米量級(jí).

不難看出，這些問(wèn)題之間具有相同的內(nèi)在邏輯，從而也給人們?cè)贜P完全問(wèn)題的認(rèn)識(shí)上以啟發(fā).

6 結(jié) 語(yǔ)

NP完全問(wèn)題的相關(guān)概念十分的抽象，難以把握，無(wú)論學(xué)生或研究人員，常有相關(guān)問(wèn)題的概念錯(cuò)誤或理解模糊，本文用通俗的語(yǔ)言揭示了這些概念的本質(zhì).

在NP完全問(wèn)題的研究中，最為關(guān)鍵的是正確的研究方向，若是研究方向?yàn)椴⒉怀闪⒌闹囌`所誤導(dǎo)，則不僅會(huì)導(dǎo)致多走彎路，甚至可能是完全做無(wú)用功.其中一個(gè)最大的謬誤就是，認(rèn)為NP當(dāng)然的不等于P.這就意味著所有NP完全問(wèn)題不可能有多項(xiàng)式時(shí)間算法，因此從根本上限制了這方面的研究.許多學(xué)者包括一些專家都將其作為限制框框.這僅僅只是一些研究人員的一種個(gè)人傾向，而絕不是定論.有理由認(rèn)為其有可能甚至極可能是錯(cuò)的.還有一種傾向就是將P vs．NP問(wèn)題過(guò)分神秘化，要么宣稱該問(wèn)題不能在人類已有知識(shí)框架內(nèi)解決，要么宣稱今后很長(zhǎng)時(shí)期人類不可能解決.所有這些宣稱并無(wú)切實(shí)的依據(jù).本文詳細(xì)論述了NP完全問(wèn)題的實(shí)質(zhì)，并從多個(gè)角度，用啟發(fā)式思維方式，分析了其時(shí)間復(fù)雜度及其特性，以及可行的研究前景和研究方向.可供相關(guān)領(lǐng)域的學(xué)者參考.

致 謝

感謝湖北省自然科學(xué)基金對(duì)本研究的支持！

［1］ARORA S， BARAK B．Complexity Theory： A Modern Approach Cambridge University Press ［M］．Cambridge，2009

［2］AARONSON S．Is P versus NP formally independent［J］．Bulletin of the European Association for Theoretical Computer Science，2003，81（10）：109－136．

［3］杜丁柱，葛可一，王潔．計(jì)算復(fù)雜性導(dǎo)引［M］．北京：高等教育出版社，2002：35－57．DU ing－zhu，Ge Keyi，Wang Jie．Introduction to Computing Complexity ［M］．Peking：High Education Press，2002：35－57．（in Chinese）

［4］SARTAJSahni，Data Structures，Algorithms，and Applications in C＋＋［M］．McGraw－Hill，1998．

［5］COOK S A．The complexity of theorem proving procedures ［M］．Proceedings of Third Annual ACM Symposium，New York：on Theory of Computing，Association for Computing Machinery，1971：151－158．

［6］KARPRM．Reducibility among combinatorial problems［M］．Miller R E， Thatcher JW Plenum Press， Complexity of Computer Computations，New York：1972：85－104．

［7］LANCE Fortnow．The Status of the P Versus NP Problem［J］．Communications of the ACM，2010，52（9）：78－86．

［8］朱麗君，陳金芳．大數(shù)據(jù)下中文期刊論文被引分析［J］．武漢工程大學(xué)學(xué)報(bào)，2015，37（5）：74－78．ZHU Li－jun，CHEN Jin－fang．Citation analysis on Chinese Periodicals Under big data［J］．Journal of Wuhan Institute of Technology，2015，37（5）：74－78．（in Chinese）

［9］付 敏，戴祖旭，王道蓬．壓縮編碼的上下文樹(shù)構(gòu)造算法［J］．武漢工程大學(xué)學(xué)報(bào)，2015，37（4）：51－55．Fu Min，Dai Zuxue，WANG Dao－peng．Context tree algorithm based on compression encoding ［J］．Journal of Wuhan Institute of Technology，2015，37（4）：51－55．（in Chinese）

［10］殷秀葉．大數(shù)據(jù)環(huán)境下的相似重復(fù)記錄檢測(cè)方法［J］．武漢工程大學(xué)學(xué)報(bào)，2014，36（9）：66－69．YIN Xiu ye．Method for detecting approximately duplicate database records in big data environment［J］．Journal of Wuhan Institute of Technology，2014（9）：66－69．（in Chinese）

［11］POSA L．Hamiltonian circuits in random graphs［J］．Discrete Math，1976（14）：359－364．