P問題

P問題是具有多項式算法的判定問題。這裡的P代表Polynomial。P問題就是可以有一個確定型圖靈機在多項式時間內解決的問題。即目前那些存在O(n), O(nk), O(nlogn)等多項式時間複雜度解法的問題。比如排序問題、最小生成樹、單源最短路徑。直觀的講，我們將P問題視為可以較快解決的問題。

基本介紹

• 中文名：P問題
• 外文名：Polynomial  problem
• 學科：數學、計算機科學

概念

P問題(P-problem)具有多項式算法的判定問題。這裡P表示Polynomial一詞的第一個字母。這類問題的吸引力在於：

1.由於多項式的加法和乘法仍為一多項式，在做替換時，仍保持問題的多項式性。

2.相對容易地計算算法的總步數。

3.對於此類問題，回答“是”與“不是”均具有多項式這一性質刻畫，換言之，對此類問題而言，回答“是”與“不是”是對稱的。

支撐樹問題、匹配問題、擬陣問題、二擬陣交問題、網路流問題、中國郵路問題、最短路問題等均屬P問題。

與NP的關係

NP問題是指那些可以在非確定型圖靈機上在多項式時間內解決的問題。（在確定型圖靈機上可以在多項式時間內驗證解是否正確，但不能在多項式時間內找出最優解的問題）。非確定型圖靈機可以理解為無限個確定型圖靈機的集合。應該是說的一種強大的目前還不存在的，也與目前的計算機無法比較的一種計算機吧。也許它具備跳躍思維、能聯想能學習能推理。

NP是目前為止還未找到多項式解法的問題。對於這些問題，我們目前也不知道是否存在多項式的解法。所以叫非確定多項式問題。NP代表“Non-deterministic（非確定性）Polynomial（多項式）”而不是代表“Non-Polynomial（非多項式）。典型的NP問題是旅行商問題(TSP)。

之所以要定義NP問題，是因為通常只有NP問題才可能找到多項式的算法。NP問題如果找到了多項式解法就是P問題了。NP問題是目前為止我們還未找到多項式解法的問題。我們也不能證明它一定存在或不存在多項式解法。調查顯示有的人持肯定態度，認為NP問題一定存在多項式解法，即P=NP。有的堅信NP問題不存在多項式解法。當然也有的人持不確定態度。

人們想知道，是否所有的NP問題都是P類問題。所有對NP問題的研究都集中在一個問題上，即究竟是否有P=NP？ 目前為止這個問題還“啃不動”。但是，一個總的趨勢、一個大方向是有的。人們普遍認為，P=NP不成立，也就是說，多數人相信，存在至少一個不可能有多項式級複雜度的算法的NP問題。

發展

人們如此堅信P≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP-完全問題，也即所謂的 NPC問題。C是英文單詞“完全”的第一個字母。正是NPC問題的存在，使人們相信P≠NP。為了說明NPC問題，我們先引入一個概念——約化(Reducibility，有的資料上叫“歸約”)。

一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。 “問題A可約化為問題B”有一個重要的直觀意義：B的時間複雜度高於或者等於A的時間複雜度。也就是說，問題A不比問題B難。這很容易理解。既然問題A能用問題B來解決，倘若B的時間複雜度比A的時間複雜度還低了，那A的算法就可以改進為B的算法，兩者的時間複雜度還是相同。

NPC問題的定義非常簡單。同時滿足下面兩個條件的問題就是NPC問題。

首先，它得是一個NP問題； 然後，所有的NP問題都可以約化到它。

證明一個問題是 NPC問題也很簡單。

先證明它至少是一個NP問題， 再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足； 至於第一個NPC問題是怎么來的，下文將介紹），這樣就可以說它是NPC問題了。

既然所有的NP問題都能約化成NPC問題，那么只要任意一個NPC問題找到了一個多項式的算法，那么所有的NP問題都能用這個算法解決了，NP也就等於P 了。因此前文才說，“正是NPC問題的存在，使人們相信P≠NP”。我們可以就此直觀地理解，NPC問題目前沒有多項式的有效算法，只能用指數級甚至階乘級複雜度的搜尋。