在計算復雜性理論中，一個問題在以下情況下是 NP 完全的：

• 這是一個可以快速驗證每個解的正確性的問題（即在多項式時間內），并且暴力搜索算法可以通過嘗試所有可能的解來找到解。
• 該問題可用于模擬我們可以快速驗證解決方案是否正確的所有其他問題。 從這個意義上說，NP 完全問題是解決方案可以快速驗證的最難的問題。 如果我們能快速找到某些 NP 完全問題的解決方案，我們就能快速找到所有其他問題的解決方案，而給定的解決方案可以很容易地得到驗證。

名稱 NP-complete 是非確定性多項式時間完成的縮寫。 在這個名稱中，非確定性指的是非確定性圖靈機，這是一種在數學上形式化蠻力搜索算法思想的方法。 多項式時間是指確定性算法檢查單個解決方案或非確定性圖靈機執行整個搜索被認為快速的時間量。 完全是指能夠模擬同一復雜度等級中的所有事物的屬性。

更準確地說，問題的每個輸入都應與一組多項式長度的解相關聯，其有效性可以快速測試（在多項式時間內），這樣如果解集非空且任何輸入的輸出為是 不，如果它是空的。 這種形式的復雜問題稱為 NP，它是非確定性多項式時間的縮寫。 如果 NP 中的所有內容都可以在多項式時間內轉換為該問題，則該問題被稱為 NP-hard，即使它可能不在 NP 中。 相反，如果一個問題同時屬于 NP 和 NP-hard，則該問題是 NP-complete。 NP 完全問題代表了 NP 中最難的問題。 如果某些 NP 完全問題具有多項式時間算法，則 NP 中的所有問題都具有。 一組 NP 完全問題通常用 NP-C 或 NPC 表示。

盡管可以快速驗證 NP 完全問題的解決方案，但還沒有已知的快速找到解決方案的方法。 也就是說，隨著問題規模的增長，使用任何當前已知的算法解決問題所需的時間會迅速增加。 因此，確定是否有可能快速解決這些問題（稱為 P 與 NP 問題）是當今計算機科學中尚未解決的基本問題之一。

雖然快速計算 NP 完全問題的解決方案的方法仍未被發現，但計算機科學家和程序員仍然經常遇到 NP 完全問題。 NP 完全問題通常通過使用啟發式方法和近似算法來解決。

NP-complete 問題是 NP 中的所有決策問題的集合，其解決方案可以在多項式時間內得到驗證； NP 可以等效地定義為可以在非確定性圖靈機上在多項式時間內解決的決策問題集。 如果 NP 中的所有其他問題都可以在多項式時間內轉換（或減少）為 p，則 NP 中的問題 p 是 NP 完全問題。

不知道是否所有 NP 問題都可以快速解決——這稱為 P 對 NP 問題。 但是如果任何 NP 完全問題都可以快速解決，那么 NP 中的每個問題都可以，因為 NP 完全問題的定義表明 NP 中的每個問題都必須可以快速還原為每個 NP 完全問題（也就是說，它可以 在多項式時間內減少）。 正因為如此，人們常說 NP 完全問題比一般的 NP 問題更難或更難。

這個定義的結果是，如果我們有 C {\displaystyle \scriptstyle C} 的多項式時間算法（在 UTM 或任何其他圖靈等效抽象機上），我們可以在多項式時間內解決 NP 中的所有問題 .

NP 完全的概念是在 1971 年引入的（參見 Cook-Levin 定理），盡管 NP 完全這個術語是后來引入的。 在 1971 年的 STOC 會議上，計算機科學家之間就是否可以在確定性圖靈機上在多項式時間內解決 NP 完全問題展開了激烈的爭論。 John Hopcroft 使會議上的每個人都達成共識，即 NP 完全問題是否可以在多項式時間內解決的問題應該推遲到以后解決。