NP完全問題

國大學生數學競賽初賽的成績公佈當天，學校就在其官網上公佈了本校學生的獲獎情況。

A大平靜的校園再次躁動起來。

各大高校開始內部公佈成績，學生也都緊張地檢視獲獎名單。

以往屆的情況來看，九十分往上的學生就少有，更別說這次的賽卷難度，考試完當天卷子就已經流通在了大眾之中。

連參與過編題的特定高校教師都認定了本次賽卷的最後兩道大題的難度，堪比決賽的程度。

按平常學生的水平，七十多分就足以進入決賽，上一屆進入決賽的最低分就是七十六分，這次直接講明瞭，能考七十分就算天賦異稟。

看到決賽名單的那一刻後，大家也都釋然了，考完當天他們就差不多估算出了自己的分數，對這個結果也早已有了定論。

決賽名單上，最後一名考了六十八分，再往上看幾乎兩到三人同分，看到第三名的時候才九十二分，第二名九十三分。

最頂上的那個分數飄過視線時，眾人眼睛一恍，是他們眼神出問題了嗎？

滿分！

臥槽，這是哪個神人！

...

此時，A大的學生更為激動，在看到學校公佈的成績後，他們直接就跪了。

京市賽區進入決賽的接近百人，幾乎全被A大、B大、海城壟斷，其他大學隻有零星的幾個人進入決賽。

其中A大占了二十六個名額，在得知滿分就在自家學校時，他們心中就隱隱有了預感，肯定是宋神！

而且，據可靠訊息，非數A類的滿分選手也在他們學校，得知這個訊息後，眾人順著網線就開始探查，到處亂問。

論壇上已經有人爆出了最新帖子。

“我們物院攤牌了，滿分在我們這裡！”

“別找了大家，是陸青詞！”

“我們數院也攤牌了，是宋挽！”

“哇哢哢，雖然我沒有進決賽，但是聽到兩個滿分在咱們學校，有一種由然而生的驕傲感！”

“隻能說，這兩大神是咱們學校的扛把子，到哪都是頂尖的存在。”

“害，那你們考的怎麼樣？”

“別說了，空了最後兩道大題，前麵有的還不會寫，一查分數43分。”

“你這還算好的，我考了27分哈哈哈哈。”

“我51分還拿了個三等獎，已經很滿意了。”

“哦吼吼吼，52分路過，意滿離~”

...

外麵討論的有多激情澎湃，宋挽就在圖書館學的有多認真，簡直穩如泰山。

馬上就要考四級了，現在不快點學等著考場上哭爹喊娘嗎？

說是備考，她其實也沒怎麼將精力放在上麵，反而偷偷拿出自己的寶貝書看，七大難題的資料根本看不完，涉及的方向太廣了。

NP完全問題中，

如果任何一個NP問題都能通過一個多項式時間演算法轉換為某個NP問題，那麼這個NP問題就稱為NP完全問題，也叫做NPC問題。

即是多項式複雜程度的非確定性問題，是不確定性圖靈機在P時間內能解決的問題。

這也是世界七大數學難題之一。

它的簡單寫法是NP=P？問題就在這個問號上，到底是NP等於P，還是NP不等於P。

P類問題：所有可以在多項式時間內求解的判定問題構成P類問題。判定問題：判斷是否有一種能夠解決某一類問題的能行演算法的研究課題。NP類問題：所有的非確定性多項式時間可解的判定問題構成NP類問題。

而NP完全問題是NP類中“最難”的問題，也就是說它們是最可能不屬於P類的，這是因為任何NP中的問題可以在多項式時間內變換成為任何特定NP完全問題的一個特例。

舉例敘述一下。

在一個週六的晚上，你參加了一個盛大的晚會，由於感到侷促不安，你想知道這一大廳中是否有你已經認識的人。你的主人向你提議說，你一定認識那位正在甜點盤附近角落的女士，不費一秒鐘，你就能向那裡掃視，並且發現你的主人是正確的。

然而，如果沒有這樣的暗示，你就必須環顧整個大廳，一個個地審視每一個人，看是否有你認識的人。

所以說，生成問題的一個解通常比驗證一個給定的解時間花費要多得多，這是這種一般現象的一個例子。

與此類似的是，如果某人告訴你，數13，717，421可以寫成兩個較小的數的乘積，你可能不知道是否應該相信他，但是如果他告訴你，他可以因式分解為3607乘3803，那麼你就可以用一個袖珍計算器容易驗證這是對的。

因此我們可以發現，所有的完全多項式非確定性問題，都可以轉換為一類叫做滿足性問題的邏輯運算問題。

既然這類問題的所有可能答案，都可以在多項式時間內計算，於是我們就會猜想，是否這類問題，存在一個確定性演算法，可以在多項式時間內，直接算出或是搜尋出正確的答案呢

這就是著名的NP=P的猜想。

有些計算問題是確定性的，比如加減乘除之類，你隻要按照公式推導，按部就班一步步來，就可以得到結果。

但是，有些問題是無法按部就班直接地計算出來，比如，找大質數的問題，下一個質數應該是多少呢有沒有一個公式，一套公式就可以一步步推算出來，很顯然，這樣的公式是沒有的。

這種問題的答案，是無法直接計算得到的，隻能通過間接的“猜算”來得到結果，這就是非確定性問題。

而這些問題的通常有個演算法，它不能直接告訴你答案是什麼，但可以告訴你，某個可能的結果是正確的答案還是錯誤的答案，這個可以告訴你“猜算”的答案正確與否的演算法，假如可以在多項式時間內算出來，就叫做多項式非確定性問題。

而如果這個問題的所有可能答案，都是可以在多項式時間內進行正確與否的驗算的話，就叫完全多項式非確定問題。