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

2026-07-07 18:58 本頁面

【正文】上，這個問題就是我們后面要說的NPC問題。下面引入P類問題的概念：如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。P是英文單詞多項式的第一個字母。哪些問題是 P類問題呢？通常NOI和NOIP不會出不屬于P類問題的題目。我們常見到的一些信息奧賽的題目都是P問題。道理很簡單，一個用窮舉換來的非多項式級時間的超時程序不會涵蓋任何有價值的算法。接下來引入NP問題的概念。這個就有點難理解了，或者說容易理解錯誤。在這里強調（回到我竭力想澄清的誤區上），NP問題不是非P類問題。NP問題是指可以在多項式的時間里驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。比方說，我RP很好，在程序中需要枚舉時，我可以一猜一個準。現在某人拿到了一個求最短路徑的問題，問從起點到終點是否有一條小于100個單位長度的路線。它根據數據畫好了圖，但怎么也算不出來，于是來問我：你看怎么選條路走得最少？我說，我RP很好，肯定能隨便給你指條很短的路出來。然后我就胡亂畫了幾條線，說就這條吧。那人按我指的這條把權值加起來一看，嘿，神了，路徑長度98，比100小。于是答案出來了，存在比100小的路徑。別人會問他這題怎么做出來的，他就可以說，因為我找到了一個比100 小的解。在這個題中，找一個解很困難，但驗證一個解很容易。驗證一個解只需要O(n)的時間復雜度，也就是說我可以花O(n)的時間把我猜的路徑的長度加出來。那么，只要我RP好，猜得準，我一定能在多項式的時間里解決這個問題。我猜到的方案總是最優的，不滿足題意的方案也不會來騙我去選它。這就是NP問題。當然有不是NP問題的問題，即你猜到了解但是沒用，因為你不能在多項式的時間里去驗證它。下面我要舉的例子是一個經典的例子，它指出了一個目前還沒有辦法在多項式的時間里驗證一個解的問題。很顯然，前面所說的Hamilton回路是NP問題，因為驗證一條路是否恰好經過了每一個頂點非常容易。但我要把問題換成這樣：試問一個圖中是否不存在Hamilton回路。這樣問題就沒法在多項式的時間里進行驗證了，因為除非你試過所有的路，否則你不敢斷定它“沒有Hamilton回路”。之所以要定義NP問題，是因為通常只有NP問題才可能找到多項式的算法。我們不會指望一個連多項式地驗證一個解都不行的問題存在一個解決它的多項式級的算法。相信讀者很快明白，信息學中的號稱最困難的問題——“NP問題”，實際上是在探討NP問題與P類問題的關系。很顯然，所有的P類問題都是NP問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解——既然正解都出來了，驗證任意給定的解也只需要比較一下就可以了。關鍵是，人們想知道，是否所有的NP問題都是P類問題。我們可以再用集合的觀點來說明。如果把所有P類問題歸為一個集合P中，把所有 NP問題劃進另一個集合NP中，那么，顯然有P屬于NP。現在，所有對NP問題的研究都集中在一個問題上，即究竟是否有P=NP？通常所謂的“NP問題”，其實就一句話：證明或推翻P=NP。NP問題一直都是信息學的巔峰。巔峰，意即很引人注目但難以解決。在信息學研究中，這是一個耗費了很多時間和精力也沒有解決的終極問題，好比物理學中的大統一和數學中的歌德巴赫猜想等。目前為止這個問題還“啃不動”。但是，一個總的趨勢、一個大方向是有的。人們普遍認為，P=NP不成立，也就是說，多數人相信，存在至少一個不可能有多項式級復雜度的算法的NP問題。人們如此堅信P≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP完全問題，也即所謂的 NPC問題。C是英文單詞“完全”的第一個字母。正是NPC問題的存在，使人們相信P≠NP。下文將花大量

點擊復制文檔內容

公司管理相關推薦

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

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

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

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

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

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

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

現狀和問題-資料下載頁

和倍問題-資料下載頁

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

p2p網貸風控之真問題-資料下載頁

酒店常見問題及處理p12-資料下載頁

中醫解釋眼睛干澀是肝問題-資料下載頁

靜力學問題和動力學問題-資料下載頁

8作風問題本質上是一個政治問題-資料下載頁

假設檢驗問題的p值法-資料下載頁

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

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

什么是p問題、np問題和npc問題-wenkub

什么是p問題、np問題和npc問題(已修改)