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 是皇后，則另一皇后必不可在打叉的方格子，只有空格可以放。
- 先放在 [0,0] 的位置
- 再來往第二列 (row 2) 找適合可以擺第二個皇后 Q2 的位置。
（圖片來源：geeksforgeeks）
擺放 Q2。看來 Q3 不能再擺了，因為前後橫向、縱向、對角線都會碰到其他皇后。
- 倒帶回去重新放 Q2 的位置，並放在 [1,3]
4.看起來可行，繼續往下放 Q3，但 Q4 也沒辦法放。
- 所以重新調整 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 都還沒有人證明的出來，依然是懸案。
有兩種可能：
- 用 DTM （目前電腦）解 NP 問題只能用暴力法，更有效率的演算法並不存在，所以P≠NP。
- 用 DTM 處理 NP 問題的更高效率演算法其實存在，只是目前還沒被找到， 所以P=NP。
「沒找到」並不等於「不存在」，如果能夠證明 P=NP，就代表人類有一天一定可以找到更高效率的演算法處理 N皇后的問題。
停機問題（Halting Problem）
有一個著名的大獎難題，被證明為「不可能」由電腦解決，那就是停機問題。
停機問題的定義
問題是這樣的：
有沒有一個程式，可以判斷輸入的程式碼是會一直運行下去，還是最終會停止（中止）？
答案是：沒有。
我一開始對於這個問題感到困惑，有什麼好問的？但其實這是個深奧的問題。數學家艾倫·圖靈（Alan Turing）早在 1936 年就證明了這個問題無法被解決，這個理論限制了電腦能夠解決的問題範圍。
假設有一個能解決停機問題的程式
假設有個神奇的程式，叫 opposite（相反），這個程式可以檢測其他程式是否會停止。如果 opposite 偵測到輸入的程式會停止，它就回傳「中止」；如果它偵測到程式會無限運行，它就回傳「持續運行」（running）。
聽起來還不錯？但接下來，我們要進一步思考：如果我們把 opposite 程式自己當作輸入，會發生什麼？
矛盾產生
現在，假設我們把 opposite 程式自己輸入給自己，也就是把「判斷程式」拿來判斷自己。會發生什麼情況呢？
- 如果 opposite 判斷自己會停止，根據它的設計，它應該回傳「持續運行」——這和它本來應該回傳的「停止」相矛盾。
- 如果 opposite 判斷自己會無限運行，它應該回傳「中止」，但這又和它的檢測結果（持續運行）矛盾。
這樣就形成了邏輯上的悖論，也就是說，這個程式無法正確地判斷自己會不會停下來。
結論
因此，無論這個程式多麼聰明，當你問它關於它自己的運行狀況時，它都會陷入邏輯矛盾，無法正確回答。這就是圖靈所證明的停機問題的核心：對於所有可能的程式，我們無法設計出一個可以總是正確判斷它們是否會停下來的程式。
推薦參考以下這兩個影片會更容易了解：
The Halting Problem: The Unsolvable Problem
Understanding the Halting Problem
- 回溯法（Backtracking）
- N-Queens ( N 皇后問題）(Leetcode 51.)
- 在介紹 P 問題之前，我們先來了解圖靈機
- DTM（Deterministic Turing Machine，決定性圖靈機）
- NTM（Non-deterministic Turing Machine，非決定性圖靈機）
- 舉個簡單的例子：
- P 問題和 NP 問題
- P 問題（Polynomial Time Problem，多項式時間問題）
- NP 問題（Non-deterministic Polynomial Time Problem，非決定性多項式時間問題）
- NP 完全（NP-Complete, NPC）
- 更具體的說明
- 停機問題（Halting Problem）
- 停機問題的定義
- 假設有一個能解決停機問題的程式
- 矛盾產生
- 結論
你可能也想看
