NP問題是指存在多項式算法能夠驗證的非決定性問題，而其中NP完全問題又是最有可能不是P問題的問題類型。所有的NP問題都可以用多項式時間歸約到他們中的一個。所以顯然NP完全的問題具有如下性質：它可以在多項式時間內求解，若且唯若所有的其他的NP－完全問題也可以在多項式時間內求解。
基本介紹
- 中文名：NP問題
- 外文名：Non-Deterministic Polynomial Problems
- 縮寫：NP
- 特點：它可以在多項式時間內驗證
介紹,歷史,非確定性問題,
介紹
首先需要介紹P(Polynomial,多項式)問題.P問題是可以在多項式時間內被確定機(通常意義的計算機)解決的問題.NP(Non-Deterministic Polynomial, 非確定多項式)問題,是指可以在多項式時間內被非確定機(他可以猜,他總是能猜到最能滿足你需要的那種選擇,如果你讓他解決n皇后問題,他只要猜n次就能完成----每次都是那么幸運)解決的問題.這裡有一個著名的問題----千禧難題之首,是說P問題是否等於NP問題,也即是否所有在非確定機上多項式可解的問題都能在確定機上用多項式時間求解.
這樣一來,只要我們找到一個NPC問題的多項式解,所有的NP問題都可以多項式時間內化歸成這個NPC問題,再用多項式時間解決,這樣NP就等於P了.
有些問題很難找到多項式時間的算法（或許根本不存在），例如“找出無向圖中哈密頓迴路”問題。但如果給了該問題的一個答案，可以在多項式時間內判斷這個答案是否正確。例如說對於哈密頓迴路問題，給一個任意的迴路，很容易判斷它是否是哈密頓迴路（只要看是不是所有的頂點都在迴路中就可以了）。這裡給出NP問題的另一個定義,這種可以在多項式時間內驗證一個解是否正確的問題稱為NP問題，亦稱為驗證問題類。
簡單的說，存在多項式時間的算法的一類問題，稱之為P類問題；在多項式時間內可由非確定機解決的一類問題，稱之為NP問題。另外，很多人相信P類問題是NP問題的一個子集，但既沒有人證明出有某個問題屬於NP但不屬於P，也沒有人證明所有NP問題都能在多項式時間內有解。
歷史
1971年，史蒂芬·庫克（Stephen A. Cook）發表了 The Complexity of Theorem Proving Procedures（定理證明過程的複雜性）。把以多項式時間解決為衡量標準的問題歸成三大類，即NP(nondeterministic poly-nomial)，NP完全(NP-complete)與NP難度問題
非確定性問題
什麼是非確定性（Non-Deterministic）問題呢？有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導，按部就班一步步來，就可以得到結果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質數的問題。有沒有一個公式，你一套公式，就可以一步步推算出來，下一個質數應該是多少呢？這樣的公式是沒有的。再比如，大的合數分解質因數的問題，有沒有一個公式，把合數代進去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結果。這也就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴你答案是什麼，但可以告訴你，某個可能的結果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項式（polynomial）時間內算出來，就叫做多項式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項式時間內進行正確與否的驗算的話，就叫完全多項式非確定問題。完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去，最終便能得到結果。但是這樣算法的複雜程度，是指數關係，因此計算的時間隨問題的複雜程度成指數的增長，很快便變得不可計算了。
人們發現，所有的完全多項式非確定性問題，都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內計算，人們於是就猜想，是否這類問題，存在一個確定性算法，可以在多項式時間內，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。解決這個猜想，無非兩種可能，一種是找到一個這樣的算法，只要針對某個特定NP完全問題找到一個算法，所有這類問題都可以迎刃而解了，因為他們可以轉化為同一個問題。另外的一種可能，就是這樣的算法是不存在的。那么就要從數學理論上證明它為什麼不存在。
有些看來好像是非多項式的問題，其實是多項式問題，只是人們一時還不知道它的多項式解而已。
