P/NP 問題、NPC問題、停機問題、N皇后問題

並不是所有問題都能透過程式來解決。在計算機理論（英語：Theory of computation）中，數學家們對各種問題進行分類，其中有許多被定義為非常難解的問題。在程式設計的世界裡，我們有各式各樣的演算法用來解決不同的問題，這些問題也可以根據它們的難度來分類。

本篇文章會帶你了解 P/NP 問題，這是計算理論中非常重要的一個主題。學習了這些概念後，當你聽到工程師們討論「P 問題」或「NP 問題」時，你就能跟上他們的思路，甚至加入討論了！

溫故知新：

演算法 | Big O 複雜度| Pseudocode 偽代碼

相關電影推薦：《模仿遊戲》（英語：The Imitation Game）

在程式設計中，有些問題必須採用「土法煉鋼」的方式來解決，也就是要一一嘗試每個可能性，直到找到正確答案。這樣的方法雖然能解決問題，但通常效率非常低，特別是當可能性很多時。

回溯法（Backtracking）

比土法煉鋼更有效的一種方法是回溯法（Backtracking）。回溯法的策略是列出所有可能性，但只要計算到某個路徑的結果已經確定不可行，就立即「回溯」並停止探索該路徑，轉而嘗試其他可能。這樣可以避免不必要的計算，節省大量時間。經典的回溯法例子就是 N 皇后問題。

N-Queens ( N 皇后問題）(Leetcode 51.)

如果有在 Leetcode 上刷題的朋友應該會對這題有印象。

我們先縮小範圍，用 4 乘 4 的棋盤來看。西洋旗的規則中，若要讓兩皇后無法吃掉彼此，則一皇后不能在另一皇后縱向、橫向或對角線。本次的挑戰是把 Q1~ Q4 四個皇后中，並符合西洋棋的規則。

以下圖來說，Q1 是皇后，則另一皇后必不可在打叉的方格子，只有空格可以放。

1. 先放在 [0,0] 的位置
2. 再來往第二列 (row 2) 找適合可以擺第二個皇后 Q2 的位置。

（圖片來源：geeksforgeeks）

3. 倒帶回去重新放 Q2 的位置，並放在 [1,3]

4.看起來可行，繼續往下放 Q3，但 Q4 也沒辦法放。

5. 所以重新調整 Q1 的位置，再填上 Q2。其實應該要先填 [1,0] 這個位置，不過這個也行不通，所以填 [3,1]，後續依序填上 Q3 和 Q4。

在介紹 P 問題之前，我們先來了解圖靈機

圖靈機（Turing Machine） 是一個能進行計算的理論模型，可以被視為現代電腦的雛形。它模擬了運算過程中的基本步驟，因此在計算理論中扮演著重要的角色。

DTM（Deterministic Turing Machine，決定性圖靈機）

DTM 的特色在於「下一步只有一種可能」。也就是說，每當圖靈機執行到某個狀態時，它只能按照一個明確的規則來決定下一個動作。現代的電腦就是屬於這種類型，因為它們的運算是決定性的。

決定性（deterministic） 的意思就是「結果是確定的」，就像你按下按鈕，電腦就會確定進行下一步操作。

NTM（Non-deterministic Turing Machine，非決定性圖靈機）

NTM 則有點特別，它的「下一步可以有多種可能性」。換句話說，它可以同時運算多個選擇，就像是在平行宇宙中同時進行多個運算。這並不是現實中的電腦能做到的，但在理論上，我們會用 NTM 來描述一些複雜問題的解法。

舉個簡單的例子：

假設我想飛到越南，面前有三個航班：BR-396、AJ-381、TK1888，但我沒有機票資訊，不知道哪一班飛越南。如果是 DTM 的情境，我只能一班班搭去試，直到找到正確的航班；這就像我一步一步按照確定的順序操作。而 NTM 的情境則像是我有分身，能同時搭上三個航班，瞬間知道哪一班飛越南，或者我超級會猜，直接猜中正確的班機。這就是 NTM 能同時探索多種可能性的特點。

P 問題和 NP 問題

在介紹 P 問題和 NP 問題之前，先了解它們與運算時間複雜度有關。

演算法 | Big O 複雜度| Pseudocode 偽代碼

P 問題（Polynomial Time Problem，多項式時間問題）

P 問題指的是那些能在多項式時間內解決的問題。簡單來說，時間複雜度用 n 來表示輸入的大小，而 P 問題的時間複雜度像是 O(n²)、O(n·log n)、O(n)、O(1) 這樣的形式，n 在底數，這表示隨著輸入的增大，運算時間增加得比較「溫和」，不會成倍爆炸。

這類問題是計算速度較快且可行的。換句話說，我們可以在合理的時間內找到解。

NP 問題（Non-deterministic Polynomial Time Problem，非決定性多項式時間問題）

NP 問題則是在 DTM 中需要用超多項式時間解的問題，n會在指數，例如O(2ⁿ)、O(nⁿ)。理論上可以用 NTM 來解決的問題，但時間複雜度比 P 問題高很多。這類問題的解法通常被形容為「土法煉鋼」，因為解決這些問題需要非常多的嘗試。

白話文來說，NP 問題就是那些解起來超難、時間超長的問題。經典的例子之一就是「八皇后問題」，你得一個一個位置嘗試，直到找到所有皇后都不互相攻擊的位置。

NP 完全（NP-Complete, NPC）

NP 完全問題（NPC） 是 NP 類別中最難的一群問題。這類問題有一個特性，就是 NP 中的其他問題都可以「化約（reduce）」成 NPC 問題。換句話說，如果你能夠解決某個 NPC 問題，代表你可以解決 NP 中的所有問題。

更具體的說明

假設我們有兩個問題：A 問題 和 A+ 問題。其中，A+ 問題比 A 問題更難（時間複雜度高）。如果你能把 A 問題「化約」成 A+ 問題，那麼你就能用解 A+ 問題的方法來解決 A 問題。但反過來，更難的問題 A+ 不能被降級成 A 問題，也就是說，解決更難的問題並不會直接幫助你解決比較簡單的問題。

總結一下，如果你能解決 NP 完全問題（A+），那麼你一定能解決 NP 問題（A）。一旦找到能有效解決 NPC 問題的演算法，那麼 NP 中的所有問題都能被高效解決！

是否存在更高效率的演算法，可使確定型圖靈機以多項式時間求 NP 問題的解？

這個是千禧年大獎難題之一，到 2024 都還沒有人證明的出來，依然是懸案。

有兩種可能：

1. 用 DTM （目前電腦）解 NP 問題只能用暴力法，更有效率的演算法並不存在，所以P≠NP。
2. 用 DTM 處理 NP 問題的更高效率演算法其實存在，只是目前還沒被找到， 所以P=NP。

「沒找到」並不等於「不存在」，如果能夠證明 P=NP，就代表人類有一天一定可以找到更高效率的演算法處理 N皇后的問題。

停機問題（Halting Problem）

有一個著名的大獎難題，被證明為「不可能」由電腦解決，那就是停機問題。

停機問題的定義

問題是這樣的：

有沒有一個程式，可以判斷輸入的程式碼是會一直運行下去，還是最終會停止（中止）？

答案是：沒有。

我一開始對於這個問題感到困惑，有什麼好問的？但其實這是個深奧的問題。數學家艾倫·圖靈（Alan Turing）早在 1936 年就證明了這個問題無法被解決，這個理論限制了電腦能夠解決的問題範圍。

假設有一個能解決停機問題的程式

假設有個神奇的程式，叫 opposite（相反），這個程式可以檢測其他程式是否會停止。如果 opposite 偵測到輸入的程式會停止，它就回傳「中止」；如果它偵測到程式會無限運行，它就回傳「持續運行」（running）。

聽起來還不錯？但接下來，我們要進一步思考：如果我們把 opposite 程式自己當作輸入，會發生什麼？

矛盾產生

現在，假設我們把 opposite 程式自己輸入給自己，也就是把「判斷程式」拿來判斷自己。會發生什麼情況呢？

1. 如果 opposite 判斷自己會停止，根據它的設計，它應該回傳「持續運行」——這和它本來應該回傳的「停止」相矛盾。
2. 如果 opposite 判斷自己會無限運行，它應該回傳「中止」，但這又和它的檢測結果（持續運行）矛盾。

這樣就形成了邏輯上的悖論，也就是說，這個程式無法正確地判斷自己會不會停下來。

結論

因此，無論這個程式多麼聰明，當你問它關於它自己的運行狀況時，它都會陷入邏輯矛盾，無法正確回答。這就是圖靈所證明的停機問題的核心：對於所有可能的程式，我們無法設計出一個可以總是正確判斷它們是否會停下來的程式。

推薦參考以下這兩個影片會更容易了解：

The Halting Problem: The Unsolvable Problem

Understanding the Halting Problem