P類問題

複雜度類P即為所有可以由一個確定型圖靈機在多項式表達的時間內解決的問題；類NP由所有可以在多項式時間內驗證它的解是否正確的決定問題組成，或者等效的説，那些可以在非確定型圖靈機上在多項式時間內找出解的問題的集合。很可能，計算理論最大的未解決問題就是關於這兩類的關係的：P和NP相等 ^[2]  。

在2002年對於100研究者的調查，61人相信答案是否定的，9個相信答案是肯定的，22個不確定，而8個相信該問題可能和所接受的公理獨立，所以不可能證明或證否 ^[2]  。

用確定的圖靈機以多項式時間界可解的問題稱為P類問題；用不確定的圖靈機以多項式時間界可解的問題稱為NP類問題 ^[3]  。

所謂P類和NP類，都是指問題的集合。由於確定的圖靈機可以看作不確定的圖靈機的一種特殊情形，因此這兩類問題的集合之間存在子集關係，即P屬於NP ^[3]  。

NP-完全問題( Np-complete problem)是計算複雜性理論中最重要的一部分內容。在計算科學和計算機科學理論中，NP完全問題也有着十分重要的地位。因為其重要性,NP-完全問題理論已發展成為一個獨立的學科分支 ^[3]  。

粗略地説,NP完全問題是這樣的一大類問題：如果對該類中的某一個問題設計出多項式時間複雜性的電子計算機算法，那麼該類中的每一個問題也都存在多項式時間複雜性的電子計算機算法；反之,如果證明了該類中的某一個問題不存在多項式時間的電子計算機算法，那麼該類中的所有問題也不可能存在多項式時間複雜性的電子計算機算法 ^[3]  。

雖然NP完全問題的研究目標是為了確定一大類問題是否存在多項式時間複雜性的電子計算機算法，但在研究方法和手段上,還是藉助圖靈機這種計算模型。具體地説,確定的圖靈機和不確定的圖靈機在計算複雜性上的差異是NP-完全問題研究的出發點 ^[3]  。

矩陣乘法是一個P類問題。對兩個n階方陣的乘積，即使採用求內積分別求積矩陣中各個元素的方法，其時間界也只有

(n³)，如果採用矩陣乘法的 Stressen算法或凝聚算法,，則可以使時間界進一步降低 ^[3]  。

多項式求值問題是一個P類問題。若採用 Horner算法對n次多項式求值,其時間界是n的線性函數。線性函數是一次多項式函數 ^[3]  。

查找問題是一個P類問題。在n個有序的數集合{a₁,a₂,…,a_n}中查找一個數b，若採用二分查找算法，其時間複雜度僅為

(log₂n)，這是比線性時間界還要低得多的一個複雜度，當然也是多項式時間界的 ^[3]  。

P類問題還有許多，不再一一列舉 ^[3]  。

大多數理論計算機科學家相信P≠NP,是因為他們確實找到一類問題NPC，這類問題有令人非常驚奇的性質，即如果NPC中任何一個問題能夠在多項式時間內找到最優解，則NP中的每個問題都能在多項式時間內找到最優解，即P=NP。儘管研究了大半個世紀，但是還沒有找到任何一個NPC問題的多項式時間算法。在給出NPC的定義之前，我們先介紹問題約簡的概念 ^[4]  。

直觀地，如果一個問題Q的任一實例能夠容易地轉化為另一個問題Q'的一個實例，則説問題Q能夠約簡到問題Q，這樣問題Q'實例的解就可以看作問題Q相應實例的解。例如解線性方程的問題可以約簡到解二次方程。例如線性方程的一個實例ax+b=0可以轉化為二次方程的一個實例0x2+ax+b=0，這樣實例0x2+ax+b=0的解就是實例ax+b=0的解。這樣問題Q能夠約簡到問題Q,從某種意義上説，Q不會比Q'更難解 ^[4]  。

雖然百萬美元的獎金和投入巨大卻沒有實質性結果的大量研究足以顯示該問題是困難的，但是還有一些形式化的結果證明為什麼該問題可能很難解決 ^[5]  。

最常被引用的結果之一是設計神諭。假想你有一個魔法機器可以解決單個問題，例如判定一個給定的數是否為質數，可以瞬間解決這個問題。我們的新問題是，若我們被允許任意利用這個機器，是否存在我們可以在多項式時間內驗證但無法在多項式時間內解決的問題？結果是，依賴於機器能解決的問題，P=NP和P≠NP二者都可以證明。這個結論帶來的後果是，任何可以通過修改神諭來證明該機器的存在性的結果不能解決問題。不幸的是，幾乎所有經典的方法和大部分已知的方法可以這樣修改（我們稱它們為相對化） ^[5]  。

如果這還不算太糟的話，1993年Razborov和Rudich證明的一個結果表明，給定一個特定的可信的假設，在某種意義下“自然”的證明不能解決P=NP問題 ^[5]  。