P 和 NP 實際上是相同的複雜度類別嗎？
P 是否等於 NP 的問題是計算機科學和數學中最深刻且尚未解決的問題之一。這個問題是計算複雜性理論的核心，該理論研究計算問題的固有難度並根據解決問題所需的資源對它們進行分類。
要理解這個問題，必須掌握 P 類和 NP 類的定義。 P 類由決策問題（具有是/否答案的問題）組成，可以透過確定性圖靈機在多項式時間內解決。多項式時間意味著解決問題所需的時間可以表示為輸入大小的多項式函數。 P 中的問題範例包括對數字列表進行排序（可以使用歸併排序等高效演算法在O(n log n) 時間內完成）以及使用歐幾里德演算法來找出兩個整數的最大公約數（其運行時間為O(log （分鐘（a，b）））時間）。
另一方面，NP 類別由決策問題組成，給定的解決方案可以透過確定性圖靈機在多項式時間內驗證。這意味著，如果有人為問題提供了候選解決方案，則可以有效地檢查其正確性。重要的是，NP並不一定意味著問題本身可以在多項式時間內解決，只是意味著所提出的解決方案可以快速驗證。 NP 中的問題範例包括布林可滿足性問題 (SAT)，其中人們試圖確定是否存在使給定布林公式為真的變數的真值分配，以及哈密頓循環問題，該問題詢問是否存在循環只訪問圖的每個頂點一次。
P vs NP 問題詢問是否每個可以在多項式時間內驗證其解決方案的問題（即 NP 中的每個問題）也可以在多項式時間內解決（即在 P 中）。形式上，問題是 P = NP 是否。如果P等於NP，則表示每個可以快速驗證解決方案的問題也可以快速解決。這將對密碼學、優化和人工智慧等領域產生深遠的影響，因為許多當前棘手的問題可能會得到有效解決。
儘管經過數十年的研究，P 與 NP 的問題仍懸而未決。尚未有人能夠證明 P = NP 或 P ≠ NP。這個問題被克萊數學研究所列為七大「千禧年獎問題」之一，正確答案者將獲得 1 萬美元的獎金，凸顯了這個問題的難度。缺乏解決方案導致了理論和應用電腦科學的重大發展。
與 P vs NP 問題相關的關鍵概念之一是 NP 完整性。如果一個問題是 NP 的並且與 NP 中的任何問題一樣難，則該問題是 NP 完全的，即任何 NP 問題都可以使用多項式時間歸約來歸約。 NP 完整性的概念是由 Stephen Cook 在 1971 年的開創性論文中引入的，他在論文中證明了 SAT 問題是 NP 完整性的。這個結果被稱為庫克定理，具有開創性，因為它提供了 NP 完全問題的具體示例，並建立了識別其他 NP 完全問題的框架。
從那時起，許多其他問題被證明是NP完整的，例如旅行商問題、派系問題和背包問題。 NP完全性的意義在於，如果任何NP完全問題可以在多項式時間內解決，那麼NP中的每個問題都可以在多項式時間內解決，這意味著P = NP。相反，如果任何 NP 完全問題無法在多項式時間內求解，則 P ≠ NP。
為了說明 NP 完備性的概念，請考慮旅行商問題 (TSP)。在此問題中，推銷員必須訪問一組城市，每個城市恰好一次，然後返回起始城市，目標是最小化總行程距離。 TSP 的決策版本詢問是否存在總距離小於或等於給定值的城市的旅行。這個問題屬於 NP 問題，因為給定一個提議的旅行，人們可以輕鬆地在多項式時間內驗證該旅行是否滿足距離約束。此外，TSP 是 NP 完全的，因為 NP 中的任何問題都可以在多項式時間內轉換為 TSP 的實例。
另一個例子是派系問題，它詢問給定的圖表是否包含指定大小的完整子圖（派系）。這個問題屬於 NP 問題，因為給定一個候選團，我們可以在多項式時間內驗證它是否確實是所需規模的團。派系問題也是 NP 完全問題，這意味著有效解決它意味著所有 NP 問題都可以有效解決。
P vs NP 和 NP 完整性的研究導致了理論計算機科學中各種技術和工具的發展。其中一種技巧是多項式時間約簡的概念，它用來顯示一個問題至少與另一個問題一樣困難。從問題 A 到問題 B 的多項式時間歸約是一種在多項式時間內將 A 的實例轉換為 B 的實例的變換，這樣 B 的變換實例的解可用於求解 A 的原始實例。內簡化為問題B，B可以在多項式時間內求解，則A也可以在多項式時間內求解。
另一個重要的概念是近似演算法的概念，它在多項式時間內為 NP 困難問題（至少與 NP 完全問題一樣困難的問題）提供近乎最優的解決方案。雖然這些演算法不一定能找到確切的最佳解決方案，但它們透過提供接近最佳解決方案，提供了處理棘手問題的實用方法。例如，旅行商問題有一個眾所周知的近似演算法，可以保證旅行在測量 TSP 的最佳旅行的 1.5 倍之內（其中距離滿足三角不等式）。
解決 P 與 NP 問題的影響超出了理論計算機科學的範圍。在密碼學中，許多加密方案依賴於某些問題的硬度，例如整數分解和離散對數，這些問題被認為屬於 NP 而不是 P。系統的安全性。相反，證明 P ≠ NP 將為此類系統的安全性提供更堅實的基礎。
在最佳化中，許多現實問題，例如調度、路由和資源分配，都被建模為 NP 困難問題。如果 P 等於 NP，則意味著可以開發有效的演算法來最佳地解決這些問題，從而為各個行業帶來重大進步。然而，目前 P ≠ NP 的假設導致了啟發式和近似演算法的發展，為這些問題提供了實用的解決方案。
P 與 NP 問題也具有哲學意義，因為它涉及數學真理的本質和人類知識的限制。如果 P 等於 NP，則意味著每個帶有簡短證明的數學陳述都可以被有效地發現，從而可能徹底改變數學發現的過程。另一方面，如果 P ≠ NP，則表示有效計算和驗證的內容有固有限制，凸顯了數學結構的複雜性和豐富性。
儘管 P 與 NP 問題缺乏明確的答案，但圍繞它的研究使人們對計算複雜性有了更深入的了解，並開發了許多對計算機科學產生深遠影響的技術和工具。解決這個問題的探索繼續激勵和挑戰研究人員，推動該領域的進步並擴大我們對計算基本極限的理解。
最近的其他問題和解答 複雜:
- PSPACE 類別不等於 EXPSPACE 類別嗎？
- P 複雜性類別是 PSPACE 類別的子集嗎？
- 我們能否透過為確定性 TM 上的任何 NP 完全問題找到有效的多項式解來證明 Np 和 P 類相同？
- NP 類別可以等於 EXPTIME 類別嗎？
- PSPACE 中是否存在沒有已知 NP 演算法的問題？
- SAT 問題可以是 NP 完全問題嗎？
- 如果存在可以在多項式時間內解決問題的非確定性圖靈機，那麼問題是否可以屬於 NP 複雜性類別
- NP 是具有多項式時間驗證器的語言類別
- P 複雜性類別中的每個上下文無關語言都是如此嗎？
- NP 作為一類具有多項式時間驗證器的決策問題的定義與 P 類問題也具有多項式時間驗證器的事實之間是否存在矛盾？