資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究為什麼NP完全問題很重要？
**非確定性多項式 (NP) 問題** 理解起來稍微困難一些。在解決NP問題方面，執行時間不可能是多項式的。它可能是 O(n!) 或更大的東西。
但是，對於這類問題，給定一個特定的解決方案，檢查該解決方案將具有多項式執行時間。
例如，數獨遊戲。
NP難問題
如果一個問題的求解演算法可以轉化為解決任何NP問題，則稱該問題為NP難問題。然後我們可以說，這個問題至少與任何NP問題一樣難，但它可能更難或更復雜。
NP完全問題
NP完全 (NPC) 問題是指同時存在於NP和NP難類中的問題。也就是說，NP完全問題可以在多項式時間內驗證，並且任何NP問題都可以多項式時間內規約到這個問題。
如果一個問題屬於NP類並且與NP類中任何問題一樣難，則該問題屬於NPC類。如果NP類中的所有問題都可以在多項式時間內規約到它，即使它本身可能不在NP類中，則該問題是NP難問題。
如果對於這些問題中的任何一個存在多項式時間演算法，則NP中的所有問題都將可以多項式時間求解。這些問題稱為NP完全問題。NP完全現象在理論和實踐上都具有重要意義。
NP完全語言很重要
NP完全語言很重要，因為所有NP完全語言都被認為具有相似的難度，因為解決其中一個意味著其他問題也被解決了。
如果一些NP完全語言被證明屬於P類，那麼所有NP都被證明屬於P類。因為，請注意，任何NP語言都可以規約到一個NP完全語言。使用此規約和給定NP完全問題的演算法來解決NP中的任何問題。因此，它們都將具有多項式時間解決方案。
如果某個NP完全語言不屬於P類，則意味著該語言屬於NP類但不屬於P類，因此這證明了P類和NP類不相等。
因此，如果某個NP完全問題被證明屬於P類或不屬於P類，則可以解決P與NP問題。
更新於： 2021年6月14日
1K+ 瀏覽量
廣告