NP Theory 緒論

• Polynomial Time
• Intractability
• Optimization Problems vs. Decision Problems
• The Theory of NP
• NP-complete 證明

定義: 一個稱為多項是時間的演算法必須符合 在河裡輸入大小下，該演算法的最差情況的時間複雜度以多項式函數為限

定義: 在資訊科學領域中，若無法在最差情況下以多項式時間的演算法來解決某個問題，則稱此問題為難解的問題

問題的難解性大致可分三類:

1. 已知問題有 Polynomial Time Algorithm 可解: Shortest Path Problem, Minimal Spanning Tree Problem, Search Problem, Sort Problem
2. 時間複雜度已被證明在指數以上的 Intractability Problem: Halting Problem, 河內塔問題
3. 目前看來還沒找到 Polynomial Time Algorithm，但也無法證明沒有 Polynomial Time Algorithm 的問題

Optimization Problems(最佳化問題): 輸出為問題的最佳解
Decision Problems(決策問題): 問題的輸出只有 yes or no

最佳化問題均可找出一個對應的決策問題

Deterministic v.s. Non-Deterministic

• 決定性演算法: 這類演算法做任何事時，該演算法的下一步只有一件事可做，每個步驟都是唯一的，結果也是唯一的
• 非決定性演算法: 這類演算法做任何事時，該演算法的下一步可能有多種選擇，由於非決定性演算法每一步驟可能有無限多種選擇需要處理，故此類演算法虛假訂有一種機器可以平行處理多種選擇，但實際上這種機器並不存在

Non-Deterministic Algorithm 執行步驟

1. 猜測階段: 如果一個問題有正確解，此階段一定能將答案猜出來
2. 驗證階段: 驗證猜測階段的答案是否為真