NP COMPLETE

NP問題到底是polyn omial，還是Non omial的N，是Non

即通常所說的NP（完全）問題，簡單的寫法，是 NP=P？的問題。NP問題到底是polynomial，還是Non-Polynomial，尚無定論。不管我們編寫程式是否靈巧，判定一個答案是可以很快利用內部知識來驗證，還是沒有這樣的提示而需要花費大量時間來求解，被看作邏輯和計算機科學中最突出的問題之一。它是斯蒂文•考克（StephenCook）於1971年陳述的。
NP裡面的N，不是Non-Polynomial的N，是Non-Deterministic，P代表Polynomial倒是對的。NP就是Non-deterministic Polynomial的問題，也即是多項式複雜程度的非確定性問題。
什麼是非確定性問題呢？有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導，按部就班一步步來，就可以得到結果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質數的問題。有沒有一個公式，你一套公式，就可以一步步推算出來，下一個質數應該是多少呢？這樣的公式是沒有的。
這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結果。這也就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴你答案是什麼，但可以告訴你，某個可能的結果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項式時間內算出來，就叫做多項式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項式時間內進行正確與否的驗算的話，就叫完全多項式非確定問題。
完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去，最終便能得到結果。但是這樣算法的複雜程度，是指數關係，因此計算的時間隨問題的複雜程度成指數的增長，很快便變得不可計算了。
人們發現，所有的完全多項式非確定性問題，都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內計算，人們於是就猜想，是否這類問題，存在一個確定性算法，可以在指數時間內，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。