詳細信息

P類問題：所有可以在多項式時間內求解的判定問題構成P類問題。判定問題：判斷是否有一種能夠解決某一類問題的能行算法的研究課題。

NP類問題：所有的非確定性多項式時間可解的判定問題構成NP類問題。非確定性算法：非確定性算法將問題分解成猜測和驗證兩個階段。算法的猜測階段是非確定性的，算法的驗證階段是確定性的，它驗證猜測階段給出解的正確性。設算法A是解一個判定問題Q的非確定性算法，如果A的驗證階段能在多項式時間內完成，則稱A是一個多項式時間非確定性算法。有些計算問題是確定性的，例如加減乘除，只要按照公式推導，按部就班一步步來，就可以得到結果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質數的問題。有沒有一個公式能推出下一個質數是多少呢？這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結果。這也就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴你答案是什么，但可以告訴你，某個可能的結果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項式（polynomial）時間內算出來，就叫做多項式非確定性問題。

NPC問題：NP中的某些問題的復雜性與整個類的復雜性相關聯.這些問題中任何一個如果存在多項式時間的算法,那么所有NP問題都是多項式時間可解的.這些問題被稱為NP-完全問題(NPC問題)。

舉例敘述

在一個周六的晚上，你參加了一個盛大的晚會。由于感到局促不安，你想知道這一大廳中是否有你已經認識的人。你的主人向你提議說，你一定認識那位正在甜點盤附近角落的女士羅絲。不費一秒鐘，你就能向那里掃視，并且發現你的主人是正確的。然而，如果沒有這樣的暗示，你就必須環顧整個大廳，一個個地審視每一個人，看是否有你認識的人。

生成問題的一個解通常比驗證一個給定的解時間花費要多得多。這是這種一般現象的一個例子。與此類似的是，如果某人告訴你，數13,717,421可以寫成兩個較小的數的乘積，你可能不知道是否應該相信他，但是如果他告訴你他可以因式分解為3607乘上3803，那么你就可以用一個袖珍計算器容易驗證這是對的。人們發現，所有的完全多項式非確定性問題，都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內計算，人們于是就猜想，是否這類問題，存在一個確定性算法，可以在多項式時間內，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。 不管我們編寫程序是否靈巧，判定一個答案是可以很快利用內部知識來驗證，還是沒有這樣的提示而需要花費大量時間來求解，被看作邏輯和計算機科學中突出的問題之一。它是斯蒂文·考克于1971年陳述的。