學霸從改變開始正文卷第714章著急的李振邦燕京大學。

    宿舍區。

    「如果任何一個np問題，都能通過一個多項式時間算法，轉換為某個np問題，那麼這個np問題就稱為np完全問題……」

    「說到底，np完全問題也就是多項式複雜程度的非確定性問題……」

    「np=p？」

    「關鍵就在這個問號上面……」

    陳舟正埋首於書桌前，皺眉整理著自己的思路。

    書桌上，他從斯德哥爾摩帶回來的草稿紙，原本還存在一些空白的地方。

    但此刻，已經全部被數學公式，或是記錄的文字，給填得滿滿當當。

    「唉……」輕聲嘆了口氣，陳舟微微沉吟，「還是那個路徑，不管是不是明確，它會變化？還是不變化？」

    「如果不變化，是不是可以最終落到確定性上面，就像那些加減乘除之類的計算問題，有著明確的公式，一步一步的計算都是確定性的……」

    「但是，有些問題能按部就班直接計算出來嗎？」

    想到這的陳舟，伸手拿出一張嶄新的a4草稿紙，寫下來兩個問題。

    【找大質數的問題】

    【大的合數分解質因數的問題】

    毫無疑問，這是兩個最簡單的例子。

    也是兩個無法按部就班，一步一步直接計算出來的問題。

    沒有一個公式，可以一步步推算出來下一個質數應該是多少。

    也不存在一個公式，能夠把合數代進去，就直接算出它的分解質因數各自是多少。

    習慣性的用筆點著這兩個問題，陳舟此刻打算從最簡單的問題入手，去驗證自己的思路。

    「這兩個都是最簡單的非確定性問題，雖然沒有確定性的計算公式，但是存在一個算法，可以驗證結果的正確與錯誤……」

    「把這兩個問題的思路再延伸的話……」

    「這個算法，假如可以在多項式時間內算出來，那就變成了多項式非確定性問題……」

    「再假如這個問題的所有可能答案，都是可以在多項式時間內，通過這個算法進行正確與否的驗算，那就變成了完全多項式非確定性問題……」

    順著這個思路，陳舟開始梳理了起來。

    即使他在頒獎晚宴上，像發癔症般的抓住了那絲靈感。

    但現在直接解決np完全問題的難度，仍舊很大，甚至超出了他的預估。

    這也是他現在從最簡單的問題入手，去驗證自己的思路的原因。

    這樣做的好處有兩點。

    一是找到自己思路的死角，解決隱藏的問題。

    二是，錯題集可以發揮威力了。

    「按照一般的解法，完全多項式非確定性問題的答案，可以用窮舉法來得到，只要一個個檢驗下去，最終便能得到結果。」

    「但是，算法的問題就會凸顯出來，算法的複雜程度是指數關係，這個算法的時間，隨問題的複雜程度成指數的增長，很快就變得不可計算了。」

    「到這裡的話，就能推到np完全問題身上了，只是……」

    陳舟邊梳理，邊把問題轉移到了np完全問題上。

    這也是最初提出這個問題時，學術界的人所走的路。

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

    那麼，如果這類問題的所有可能答案，都可以在多項式時間內計算，是不是這類問題存在一個確定性算法，可以在多項式時間內直接算出或是搜尋出正確的答案呢？

    這也就是著名的np完全問題的猜想。

    現在學術界關於解決這個猜想的思路，也提出了兩種可能