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