[科普中國]-P類問題

P/NP問題是在理論信息學(xué)中計算復(fù)雜度理論領(lǐng)域里至今未被解決的問題，也是克雷數(shù)學(xué)研究所七個千禧年大獎難題之一。P/NP問題中包含了復(fù)雜度類P與NP的關(guān)系。1971年史提芬·古克（Stephen A. Cook）和Leonid Levin相對獨立地提出了下面的問題，即復(fù)雜度類P和NP是否是恒等的（P=NP?）。1

P=NP復(fù)雜度類P即為所有可以由一個確定型圖靈機(jī)在多項式表達(dá)的時間內(nèi)解決的問題；類NP由所有可以在多項式時間內(nèi)驗證它的解是否正確的決定問題組成，或者等效的說，那些可以在非確定型圖靈機(jī)上在多項式時間內(nèi)找出解的問題的集合。很可能，計算理論最大的未解決問題就是關(guān)于這兩類的關(guān)系的：P和NP相等。3

在2002年對于100研究者的調(diào)查，61人相信答案是否定的，9個相信答案是肯定的，22個不確定，而8個相信該問題可能和所接受的公理獨立，所以不可能證明或證否。對于正確的解答，有一個1,000,000美元的獎勵。1

NP-完全問題（或者叫NPC）的集合在這個討論中有重大作用，它們可以大致的被描述為那些在NP中最不像在P中的（確切定義細(xì)節(jié)請參看NP-完全理論）。計算機(jī)科學(xué)家相信P,NP，和NPC類之間的關(guān)系如圖中所示，其中P和NPC類不交。1

簡單來說，P=NP問題問道：如果實然問題的正面答案可以很快驗證，其答案是否也可以很快計算？2

這里有一個給你找點這個問題的感覺的例子：1

給定一個大數(shù)Y，我們可以問Y是否是復(fù)合數(shù)。例如，我們可能問53308290611是否有非平凡的因數(shù)。 答案是肯定的，雖然手工找出一個因數(shù)很麻煩。從另一個方面講，如果有人聲稱答案是"對，因為224737可以整除53308290611"，則我們可以很快用一個除法來驗證。 驗證一個數(shù)是除數(shù)比找出一個明顯除數(shù)來簡單得多。用于驗證一個正面答案所需的信息也稱為證明。 所以我們的結(jié)論是，給定正確的證明，問題的正面答案可以很快地（也就是，在多項式時間內(nèi)）驗證，而這就是這個問題屬于NP的原因。1

雖然這個特定的問題，最近也被證明為在P類中（參看下面的關(guān)于"質(zhì)數(shù)在P中"的參考），這一點也不明顯，而且有很多類似的問題相信不屬于類P。3

像上面這樣，把問題限制到“是/不是”問題并沒有改變原問題（即沒有降低難度）；即使我們允許更復(fù)雜的答案，最后的問題（是否FP=FNP）是等價的。2

學(xué)術(shù)定義更正式一些，一個決定問題是一個取一些字符串為輸入并要求輸出為是或否的問題。若有一個算法（譬如圖靈機(jī)，或一個LISP或Pascal的程序并有無限的內(nèi)存）能夠在最多n^k步內(nèi)對一個串長度為n的輸入給出正確答案，其中k是某個不依賴于輸入串的常數(shù)，則我們稱該問題可以在多項式時間內(nèi)解決，并且將它置入類P。直觀的講，我們將P中的問題視為可以較快解決的問題。3

假設(shè)有一個算法A(w,C)取兩個參數(shù)，一個串w，也就是我們的決定問題的輸入串，而另一個串C是“建議證明”，并且使得A在最多n^k步之內(nèi)產(chǎn)生“是/否”答案（其中n是w的長度而k不依賴于w）。進(jìn)一步假設(shè)w是一個答案為“是”的例子，當(dāng)且僅當(dāng)，存在C使得A(w,C)返回“是”。2

則我們稱這個問題可以在非決定性多項式時間內(nèi)解決，且將它放入NP類。我們把算法A作為一個所建議的證明的檢驗器，它運(yùn)行足夠快。（注意縮寫NP代表“Non-deterministic（非確定性）Polynomial（多項式）”而不是代表“Non-Polynomial（非多項式）。）2

NP完全要解決P=NP問題，NP完全的概念非常有用。不嚴(yán)格的講，NP完全問題是NP類中“最難”的問題，也就是說它們是最可能不屬于P類的。這是因為任何NP中的問題可以在多項式時間內(nèi)變換成為任何特定NP完全問題的一個特例。例如，旅行推銷員問題的判定問題版本是NP完全的。所以NP中的任何問題的任何特例可以在多項式時間內(nèi)機(jī)械地轉(zhuǎn)換成旅行商問題的一個特例。 所以若旅行商問題被證明為在P內(nèi)，則P=NP。旅行商問題是很多這樣的NP完全的問題之一。若任何一個NP完全的問題在P內(nèi)，則可以推出P=NP。不幸的是，很多重要的問題被證明為NP完全，但沒有一個有已知快速的算法。1

更難的問題雖然是否P=NP還是未知的，在P之外的問題是已經(jīng)知道存在的。尋找國際象棋或圍棋最佳走法（在n乘n棋盤上）是指數(shù)時間完全的。因為可以證明P ≠ EXPTIME（指數(shù)時間），這些問題位于P之外，所以需要比多項式時間更多的時間。判定Presburger算術(shù)中的命題是否為真的問題更加困難。Fischer和Rabin于1974年證明每個決定Presburger命題的真?zhèn)涡缘乃惴ㄓ凶钌?的運(yùn)行時間，c為某個常數(shù)。這里，n是Presburger命題的長度。因此，該命題已知需要比指數(shù)時間更多的運(yùn)行時間。不可判定問題是更加困難的，例如停機(jī)問題。它們無法在任何給定時間內(nèi)解決。2

P真的容易處理嗎？上面所有的討論，假設(shè)了P表示“容易”而“不在P中”表示“困難”。這是一個在復(fù)雜度理論中常見而且有一定準(zhǔn)確性的假設(shè)，它在實踐中卻不總是真的，原因包括如下幾點：2

它忽略了常數(shù)因子。一個需要10n時間的問題是屬于P的（它是線性時間的），但是事實上完全無法處理。一個需要102時間的問題不是在P中的（它是指數(shù)時間的），但是對于n取值直到幾千時還是很容易處理的。1

它忽略了指數(shù)的大小。一個時間復(fù)雜度n屬于P，但是很難對付。已經(jīng)證明在P中存在需要任意大的指數(shù)的問題（參看時間層次定理）。一個時間復(fù)雜度2的問題不屬于P，但對于n直到幾千還是容易應(yīng)對的。1

它只考慮了最壞情況的復(fù)雜度。1可能現(xiàn)實世界中的有些問題在多數(shù)時候可以在時間n中解決，但是很偶爾你會看到需要時間2的特例。這個問題可能有一個多項式的平均時間，但最壞情況是指數(shù)式的，所以該問題不屬于P。2

它只考慮確定性解?？赡苡幸粋€問題你可以很快解決如果你可以接受出現(xiàn)一點誤差的可能，但是確保正確的答案會難得多。這個問題不會屬于P，雖然事實上它可以很快求解。這實際上是解決屬于NP而還不知道是否屬于P的問題的一個辦法（參看RP，BPP）。2

新的諸如量子計算機(jī)這樣的計算模型，可能可以快速的解決一些尚未知道是否屬于P的問題；但是，沒有一個它們已知能夠解決的問題是NP完全的。2不過，必須注意到P和NP問題的定義是采用像圖靈機(jī)這樣的經(jīng)典計算模型的術(shù)語表述的。所以，即使一個量子計算機(jī)算法被發(fā)現(xiàn)能夠有效的解決一個NP完全問題，我們只是有了一個快速解決困難問題的實際方法，而不是數(shù)學(xué)類P和NP相等的證明。3

計算機(jī)科學(xué)家為什么認(rèn)為P≠NP？多數(shù)計算機(jī)科學(xué)家相信P≠NP。該信念的一個關(guān)鍵原因是經(jīng)過數(shù)十年對這些問題的研究，沒有人能夠發(fā)現(xiàn)一個NP完全問題的多項式時間算法。而且，人們早在NP完全的概念出現(xiàn)前就開始尋求這些算法了（Karp的21個NP完全問題，在最早發(fā)現(xiàn)的一批中，有所有著名的已經(jīng)存在的問題）。進(jìn)一步地，P = NP這樣的結(jié)果會導(dǎo)致很多驚人的結(jié)果，那些結(jié)果現(xiàn)在被相信是不成立的，例如NP = 反NP和P = PH。2

也有這樣論證的：問題較難求解（P）但容易驗證（NP），這和我們?nèi)粘＝?jīng)驗是相符的。2

從另一方面講，某些研究者認(rèn)為我們過于相信P ≠ NP，而應(yīng)該也去尋找P = NP的證明。例如，2002年中有這樣的聲明：1

“ 傾向P≠NP的主要論據(jù)是在窮盡搜索的領(lǐng)域完全沒有本質(zhì)進(jìn)展。也就是說，以我的觀點，一個很弱的論據(jù)。算法的空間是很大的，而我們只是在開始探索的起點?！M(fèi)馬最后定理的解決也顯示非常簡單的問題可能只有用非常深刻的理論才能解決。 ”1

—— Moshe Y. Vardi，萊斯大學(xué)1

“ 過分依賴某種投機(jī)的猜測不是規(guī)劃研究的一個好的導(dǎo)引。我們必須總是嘗試每個問題的兩個方向。偏見可能導(dǎo)致著名的數(shù)學(xué)家無法解決答案和他們的預(yù)計相反的著名問題，雖然他們發(fā)展了所有所需的方法。 ”3

—— Anil Nerode，康奈爾大學(xué)3

關(guān)于證明的難度的結(jié)果雖然百萬美元的獎金和投入巨大卻沒有實質(zhì)性結(jié)果的大量研究足以顯示該問題是困難的，但是還有一些形式化的結(jié)果證明為什么該問題可能很難解決。3

最常被引用的結(jié)果之一是設(shè)計神諭。假想你有一個魔法機(jī)器可以解決單個問題，例如判定一個給定的數(shù)是否為質(zhì)數(shù)，可以瞬間解決這個問題。我們的新問題是，若我們被允許任意利用這個機(jī)器，是否存在我們可以在多項式時間內(nèi)驗證但無法在多項式時間內(nèi)解決的問題？結(jié)果是，依賴于機(jī)器能解決的問題，P=NP和P≠NP二者都可以證明。這個結(jié)論帶來的后果是，任何可以通過修改神諭來證明該機(jī)器的存在性的結(jié)果不能解決問題。不幸的是，幾乎所有經(jīng)典的方法和大部分已知的方法可以這樣修改（我們稱它們在相對化）。2

如果這還不算太糟的話，1993年Razborov和Rudich證明的一個結(jié)果表明，給定一個特定的可信的假設(shè)，在某種意義下“自然”的證明不能解決P=NP問題。2

多項式時間算法沒人知道多項式時間算法對于NP完全問題是否存在。但是如果這樣的算法存在，我們已經(jīng)知道其中的一些了！例如下面的算法正確地接受了一個NP完全語言，但是沒人知道通常它需要多久運(yùn)行。它是一個多項式時間算法當(dāng)且僅當(dāng)P = NP。1

// 接受NP完全語言的一個算法子集和。1

//

// 這是一個多項式時間算法當(dāng)且僅當(dāng)P=NP。1

//

// “多項式時間”表示它在多項式時間內(nèi)返回“是”，若1

// 結(jié)果是“是”，否則永遠(yuǎn)運(yùn)行。2

//

// 輸入：S = 一個自然數(shù)的有限集1

// 輸出："是"如果某個S的子集加起來等于0。3

// 否則，它永遠(yuǎn)運(yùn)行沒有輸出。2

// 注意: "程序數(shù)P"是你將一個整數(shù)P寫為二進(jìn)制，然后2

// 將位串考慮為一個程序。2

// 每個可能的程序都可以這樣產(chǎn)生，3

// 雖然多數(shù)什么也不做因為有語法錯誤。1

//

FOR N = 1...infinity2

FOR P = 1...N2

以S為輸入運(yùn)行程序數(shù)P N步1

IF程序輸出一個不同的整數(shù)的列表1

AND所有整數(shù)都在S中1

AND整數(shù)的和為01

THEN1

OUTPUT "是"并停機(jī)1

若P = NP，則這是一個接受一個NP完全語言的多項式時間算法。“接受”表示它在多項式時間內(nèi)給出“是”的答案，但允許在答案是“否”的時候永遠(yuǎn)運(yùn)行。2

可能我們想要“解決”子集和問題，而不是僅僅“接受”子集和語言。這表示我們想要它總是停機(jī)并返回一個“是”或“否”的答案。是否存在任何可能在多項式時間內(nèi)解決這個問題的算法？沒有人知道。但是如果這樣的算法存在，那么我們已經(jīng)知道其中的一些了！只要將上面的算法中的IF語句替換成下面的語句：2

IF程序輸出一個完整的數(shù)學(xué)證明2

AND證明的每一步合法2

AND結(jié)論是S確實有（或者沒有）一個和為0的子集2

THEN2

OUTPUT "是"（或者"不是"如果那被證明了）并停機(jī)2

邏輯表述P=NP問題可以用邏輯命題的特定類的可表達(dá)性的術(shù)語來重新表述。所有P中的語言可以用一階邏輯加上最小不動點操作（實際上，這允許了遞歸函數(shù)的定義）來表達(dá)。類似地，NP是可以用存在性二階邏輯來表達(dá)—也就是，在關(guān)系、函數(shù)、和子集上排除了全稱量詞的二階邏輯。多項式等級，PH中的語言對應(yīng)與所有的二階邏輯。這樣，“P是NP的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達(dá)帶最小不動點操作的一階邏輯的所不能表達(dá)的語言？”3

這表明一些似乎最有希望的方法不太可能成功。隨著更多這類定理得到證明，該定理的可能證明方法有越來越多的陷阱要規(guī)避。3

這實際上也是為什么NP完全問題有用的原因：若對于NP完全問題存在有一個多項式時間算法，或者沒有一個這樣的算法，這將能用一種相信不被上述結(jié)果排除在外的方法來解決P=NP問題。1

花絮普林斯頓大學(xué)計算機(jī)系樓將二進(jìn)制代碼表述的“P=NP?”問題刻進(jìn)頂樓西面的磚頭上。如果證明了P=NP，磚頭可以很方便的換成表示“P=NP！”。1

康奈爾大學(xué)的Hubert Chen博士提供了這個玩笑式的P不等于NP的證明：1

反證法。設(shè)P = NP。令y為一個P = NP的證明。證明y可以用一個合格的計算機(jī)科學(xué)家在多項式時間內(nèi)驗證，我們認(rèn)定這樣的科學(xué)家的存在性為真。但是，因為P = NP，該證明y可以在多項式時間內(nèi)由這樣的科學(xué)家發(fā)現(xiàn)。但是這樣的發(fā)現(xiàn)還沒有發(fā)生（雖然這樣的科學(xué)家試圖發(fā)現(xiàn)這樣的一個證明），我們得到了矛盾。2

本詞條內(nèi)容貢獻(xiàn)者為:

尚軼倫 - 副教授 - 同濟(jì)大學(xué)數(shù)學(xué)科學(xué)學(xué)院