NP完全問題，也稱爲NP-C問題，是世界七大數學難題之一。它的英文全稱是Non-deterministic Polynomial的問題，即多項式複雜程度的非確定性問題。如果任何一箇NP問題都能通過一箇多項式時間算法轉換爲某個NP問題，那麼這個NP問題就稱爲NP完全問題。這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結果。這些問題的通常有個算法，它不能直接告訴你答案是什麼，但可以告訴你，某個可能的結果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項式時間內算出來，就叫做多項式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項式時間內進行正確與否的驗算的話，就叫完全多項式非確定性問題。完全多項式非確定性問題可以用窮舉法得到答案，一箇個檢驗下去，最終便能得到結果。但是這樣算法的複雜程度，是指數關係，因此計算的時間隨問題的複雜程度成指數的增長，很快便變得不可計算了。解決NP完全問題一般採用模擬退火法，遺傳算法，神經網絡。