正文內容

什么是p問題、np問題和npc問題(編輯修改稿)

2025-09-01 18:58 本頁面

　

【文章內容簡介】篇幅介紹NPC問題，你從中可以體會到NPC問題使P=NP變得多么不可思議。為了說明NPC問題，我們先引入一個概念——約化(Reducibility，有的資料上叫“歸約”)。簡單地說，一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。《算法導論》上舉了這么一個例子。比如說，現在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那么我們說，前者可以約化為后者，意即知道如何解一個一元二次方程那么一定能解出一元一次方程。我們可以寫出兩個程序分別對應兩個問題，那么我們能找到一個“規則”，按照這個規則把解一元一次方程程序的輸入數據變一下，用在解一元二次方程的程序上，兩個程序總能得到一樣的結果。這個規則即是：兩個方程的對應項系數不變，一元二次方程的二次項系數為0。按照這個規則把前一個問題轉換成后一個問題，兩個問題就等價了。同樣地，我們可以說，Hamilton回路可以約化為TSP問題(Travelling Salesman Problem，旅行商問題)：在Hamilton回路問題中，兩點相連即這兩點距離為0，兩點不直接相連則令其距離為1，于是問題轉化為在TSP問題中，是否存在一條長為0的路徑。Hamilton回路存在當且僅當TSP問題中存在長為0的回路。“問題A可約化為問題B”有一個重要的直觀意義：B的時間復雜度高于或者等于A的時間復雜度。也就是說，問題A不比問題B難。這很容易理解。既然問題A能用問題B來解決，倘若B的時間復雜度比 A的時間復雜度還低了，那A的算法就可以改進為B的算法，兩者的時間復雜度還是相同。正如解一元二次方程比解一元一次方程難，因為解決前者的方法可以用來解決后者。很顯然，約化具有一項重要的性質：約化具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。這個道理非常簡單，就不必闡述了。現在再來說一下約化的標準概念就不難理解了：如果能找到這樣一個變化法則，對任意一個程序A的輸入，都能按這個法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說，問題A可約化為問題B。當然，我們所說的“可約化”是指的可“多項式地”約化(Polynomialtime Reducible)，即變換輸入的方法是能在多項式的時間里完成的。約化的過程只有用多項式的時間完成才有意義。好了，從約化的定義中我們看到，一個問題約化為另一個問題，時間復雜度增加了，問題的應用范圍也增大了。通過對某些問題的不斷約化，我們能夠不斷尋找復雜度更高，但應用范圍更廣的算法來代替復雜度雖然低，但只能用于很小的一類問題的算法。再回想前面講的P和NP問題，聯想起約化的傳遞性，自然地，我們會想問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個稍復雜的大NP問題，那么最后是否有可能找到一個時間復雜度最高，并且能“通吃”所有的 NP問題的這樣一個超級NP問題？答案居然是肯定的。也就是說，存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那么所有的NP問題都解決了。這種問題的存在難以置信，并且更加不可思議的是，這種問題不只一個，它有很多個，它是一類問題。這一類問題就是傳說中的NPC 問題，也就是NP完全問題。NPC問題的出現使整個NP問題的研究得到了飛躍式的發展。我們有理由相信，NPC問題是最復雜的問題。再次回到全文開頭，我們可以看到，人們想表達一個問題不存在多項式的高效算法時應該說它“屬于NPC問題”。此時，我的目的終于達到了，我已經把NP問題和NPC問題區別開了。到此為止，本文已經寫了近5000字了，我佩服你還能看到這里來，同時也佩服一下自己能寫到這里來。

點擊復制文檔內容

公司管理相關推薦

什么是p問題、np問題和npc問題(編輯修改稿)

痛風飲食需注意什么問題-資料下載頁

chapter06運輸問題和指派問題-資料下載頁

讓孩子懂得解決什么問題-資料下載頁

懷孕需要注意什么問題-資料下載頁

[幼兒教育]問題孩子是問題家庭的代言人-資料下載頁

電磁導軌問題歸類42p-資料下載頁

面試阿姨注意什么問題-資料下載頁

問題答案和一些治理相關問題等-資料下載頁

生存和發展問題-資料下載頁

英語問題和答案-資料下載頁

口譯問題和策略-資料下載頁

黨風問題是有關黨的生死存亡的問題-資料下載頁

現狀和問題-資料下載頁

和倍問題-資料下載頁

行程問題——流水問題、過橋問題-資料下載頁

什么是p問題、np問題和npc問題(更新版)

什么是p問題、np問題和npc問題(專業版)

什么是p問題、np問題和npc問題(留存版)

什么是p問題、np問題和npc問題-文庫吧