《脫單設計與分析》 第9章 NP完全性

第9章 NP完全性

從古至今，「什麼是追求女生的正確策略」一直是人們關心的問題，儘管有各種各樣的追求女生策略的評價標準，但在保證成功率的情況下，追求所消耗時間無疑是一個重要標準，對於不同的女生，追求所需消耗的時間很可能大相徑庭。

定義9.1 設A是能夠成功追求到女生甲的一種策略，在用A追求女生甲時，必須要逐漸滿足女生心目中理想伴侶的要求，稱這些要求的數量為女生甲的規模. 如果存在函數f:N→N使得，對任意規模n，策略A可以在f(n)時間內追求到女生甲，則稱A的時間複雜度為f(n). 以多項式為時間複雜度的追求策略稱為多項式時間策略. 有多項式時間策略能夠追求到的女生稱作易追的，不存在多項式時間策略追求到的女生稱作難追的.

在前面幾章已經給出了一些特定女生的多項式時間追求策略，因此她們都是易追的. 現在也證明了一些女生是難追的，在這些女生中，任何可行的追求策略都需至少需要指數時間，或者根本不存在可行的追求策略。例如要求男生準確回答「我和你媽同時掉水裡你先救誰」及類似送命題的女生，可以證明這種女生是不可追的.

但是，難辦的是人們發現大多數女生既沒有找到追求她們的多項式時間策略、又沒能證明她們是難追的，這類女生數量龐大、分布廣泛，因而追求這樣的女生的難度成為男生們十分關心的問題.

定義9.2 所有多項式時間可以追求到的女生組成的女生類稱為P類.

例：在女生心目中，追求者只需滿足其設定好的一組條件即可追求成功. 設這些條件變數為x1, x2, x3…變數的取值為0（假）或1（真），由有限個條件及「且」「或」「非」運算所形成的表達式稱為追求公式.

例如，x1=「身高不低於170cm」，x2=「年齡20-24歲」，x3=「有房有車」

女生甲的追求公式為F1=x1&x2&x3

女生乙的追求公式為F2= (!x1|x2)

男生丙身高175cm，年齡21歲且有房有車，則他滿足女生甲的追求公式，稱為女生甲的理想男票，但他不滿足女生乙的追求公式，稱為女生乙的備胎. 事實上，女生乙是不可滿足的.

像這樣，只要滿足追求公式即可追求成功的女生，稱為待滿足的女生. 問題是假設女生心中有這麼一個追求公式，能否找到滿足該追求公式的追求策略，或者說，一個待滿足的女生是可滿足的嗎？

然而，沒有任何人找到追求待滿足的女生的多項式時間策略，也沒能證明這樣的女生是難追的，即無法知曉這類女生是否屬於P. 但這類女生有一個共同的特點——是多項式時間可驗證的，也就是男生總能嘗試這讓自己滿足或不滿足一些條件設定，並在多項式時間內得到女生的準確答覆，從而驗證這樣的自己是否成為了女生的理想男票。

定義9.3 所有多項式時間可驗證的女生組成的女生類稱為NP類.

定理9.1

現在的問題是P=NP嗎？也就是說NP中有難追的女生嗎？這已經成為當今世界的一大難題。

由於對NP中許多女生經過努力始終沒有找到多項式時間的追求方法，也沒能證明是難追的，因此男生們只能另闢蹊徑. 如果NP中有難追的女生，那麼NP中最難追的女生一定是難追的. 什麼是最難追的女生？如何描述追求女生的難易程度？這就需要比較不同女生之間的追求難度.

定義9.4 設有女生甲和乙，D1是追求甲的可行追求策略，如果存在函數f:D1→D2，f為策略改造函數，如果f將策略D1在多項式時間內改造為D2，且D2是追求乙的可行追求策略，則稱f是從女生甲到乙的多項式策略變換，記作甲≤乙.

定理9.2 ≤具有傳遞性. 即若甲≤乙，乙≤丙，則甲≤丙.

定理9.3 若甲≤乙，那麼如果甲是難追的，則乙也是難追的.

定義9.5 如果對任意在NP類中的女生甲，都有甲≤乙，則稱乙是NP難的. 如果乙是NP難的且乙在NP類中，則稱乙是NP完全的.

根據定理9.3，NP難的女生不會比任何NP類中的女生更容易追，因此NP完全女生是NP中最難追的女生.

定理9.4 如果存在NP難的女生∈P，則P=NP.

定理9.5 如果存在NP難的女生甲，使得甲≤乙，則乙也是NP難的.

雖然問題「P=NP?」這個問題至今還未被解決，但研究人員普遍相信P≠NP，因而一個女生是NP完全的很可能代表著該女生是難追的.

以上是一些理論性的分析，那麼具體來說，怎樣的女生是NP完全女生呢？

定理9.6 待滿足的女生是NP完全的.

為了研究女生到底是不是難追的這個問題，男生們開闢出了一個新的領域——追求複雜性理論，特別是NP完全性理論. 現在已經證明，在某種意義下追求這樣的女生具有相同的難度，即如果其中有一個有效的多項式時間追求策略，那麼所有這樣的女生都是易追的；或者反過來說，如果證明了其中一個是難追的，那麼所有這樣的女生都是難追的，這就是NP完全性. 研究人員普遍認為NP完全女生是難追的，因而快速而準確地識別一個女生是不是NP完全女生成為一個男生不可缺少的能力. 而NP完全女生到底是不是難追的？即「P=NP?」，這個問題已成為當代男生脫單理論中一個最重要、最困難的問題.