Formal Language - Ch15 複雜度P和NP Time Complexity, P and NP

[演算法複習] Asymptotic analysis

• Big-O and Small-O 表示法
• Big-O : $f(n) = O(g(n))$：有任何一個正整數 $c$ 和 $n_0$ 使得當$n > n_0$時  $f(n) \leq cg(n)$ 成立 (asymptotic upper bound)
• Small-O : $f(n) = o(g(n))$：$lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}=0$
  
• 常見的bounds
• Polynomial bounds : $n^c$ for some $c > 0$. 
• Exponential bounds : $2^{n^t}$ for some $t > 0$. (指數可換底，所以用2來代表)
• P與NP
• $P = \bigcup_k TIME(n^k)$：所有在決定性單紙帶TM上跑時間複雜度為$O(t(n))$的語言。
• $NP = \bigcup_k NTIME(n^k)$：所有在非決定性單紙帶TM上跑時間複雜度為$O(t(n))$的語言。

各模型間的複雜度關係

討論複雜度時會考慮三個重要的模型，分別是

• 單紙帶圖靈機
• 多紙帶圖靈機
• 非決定性圖靈機

以下是一些重要的轉換複雜度

• 單紙帶圖靈機 vs. 多紙帶圖靈機  :  最多以多項式時間可以轉換
• 決定性圖靈機 vs. 非決定性圖靈機  :  最多以指數時間可以轉換

多紙帶圖靈機轉單紙帶圖靈機

• 轉換複雜度：$t(n) = O( t^2(n) )$，差一個平方，例如，$O(n^3) \rightarrow_t O((n^3)^2) = O(n^6)$
• 解說：多紙帶TM走1步時，單紙帶TM掃$kn = O(t(n))$遍的紙帶，所以多紙帶TM走$t(n)$步時，單紙帶TM掃了$t(n) \times O(t(n)) = O( t^2(n) )$步。
• 注意：$O(t^{2(n)})$是upper bound! 可能有更好的轉換方式

非決定性圖靈機轉決定性圖靈機

• 轉換複雜度：$t(n) = 2^{O( t(n) )}$，差一個指數次方，這是目前找到的方法。
• 解說：對非決定性圖靈機的樹作迭代深度優先搜尋，把紙帶當queue，每次push 或 pop 都是$O(n)$，而樹有$2^{n-1}$個節點，因此複雜度為 $O( t(n) \times  b^{t(n)} ) =  2 ^ { O(t(n)) }$ 
• 注意：$2^{O(t(n))}$ 是upper bound，但它夠「緊」嗎?  不知道，因為這是NP = P 問題。

複雜度 P 

在計算複雜度理論中，P 是在複雜度類問題中，可用決定性圖靈機以多項式時間求解的決定性問題。

P通常表示那類可以「有效率地解決」或「溫馴」的可計算型問題，就算指數級非常高也可以算作溫馴，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要$n^{1024}$指令來解決的問題。很多情況下存在著更難的複雜度問題。

在P中令人注目的問題

P包含了很多已知的自然問題，例如決定性版本的線性規劃，計算最大公因數，以及發現最大吻合。在2002年，判別一個數是否為質數也被人解出是一個P問題。與功能性問題相關的類別是FP。

P的性質

多項式時間演算法擁有組裝封閉性。換句話說，若我寫了一個內容是多項式時間的函數，且其它被本函數呼叫的副函數也屬於多項式時間，則整個兜起來的演算法也會是多項式時間。

[舉例1] 找s到t的路線 

$PATH = \{(G, s, t)\ |\ 在一個有向圖G中，是否找的到一個從點s到點t的路線 \}$

步驟：

1. 標記點s
2. 掃所有的邊，如果有節點被指向就標記
3. 重複步驟2直到沒有節點新增
4. t被標記就接受，反之拒絕

分析：因為紙帶上是記錄圖，因此有$m^2$節點的複雜度。

$m(節點複雜度) \times m^2 (邊複雜度)= m^3 (但是和紙帶上的m^2比較) = O( n^{1.5} )$ 

[舉例2] 連通圖 connected undirected graph

$A = \{\ <G>\ |\ G\ is\ a\ connected\ undirected\ graph\ \}$

步驟：

• A TM for this problem can be given as:
• M = " On input <G>, the encoding of a graph G:
1. Select the first node of G and mark it.
2. Repeat 3) until no new nodes are marked
3. For each node in G, mark it, if there is edge attaching it to an already marked node.
4. Scan all the nodes in G. If all are marked, the accept, else reject "

[舉例3] 檢驗互質 

$REL_{PRIME} = \{ (x, y)\ |\ x 和 y互質  \}$

步驟：使用輾轉相除法（Euclidean 演算法）

分析：根據數字大小與「位數數目」的關係，放在紙帶上的數字大約是$log x+log y$

，因此步驟的總數為$max(log x , log y) = O(n)$。

[舉例4] context-free language

任何 context-free language 都在class P中 ，利用CYK 演算法來實現（動態規劃）。

複雜度 NP 
非確定性多項式時間複雜性類，包含了可以在多項式時間內，對一個判定性算法問題的實例，一個給定的解是否正確的算法問題。

NP是計算複雜性理論中最重要的複雜性類之一。它包含複雜性類P，即在多項式時間內可以驗證一個算法問題的實例是否有解的算法問題的集合；同時，它也包含NP完全問題，即在NP中「最難」的問題。計算複雜性理論的中心問題，P/NP問題即是判斷對任意的NP完全問題，是否有有效的算法，或者NP與P是否相等。


解決 solving v.s. 驗證 verifying
假如我們無法以「多項式時間(O($n^d$) time)」解決一個問題，那麼我們可以給該問題假設一個答案，接著驗證此答案是對或錯。

$A=\{ w\ |\ V\ accept\ <w,c>\ for\ some\ string\ c\ \}$

比如說，我們不知道81785036517是否為質數，但是要確定277877是否為81785036517因數，我們可以直接拿去除。針對277877來驗證8178503651是否為質數的動作可在多項式時間內完成，故針對某可能解來驗證某數是否為質數的問題是一個P問題。

因此，理解NP有兩個角度：

• 非確定性圖靈機的多項式時間可解的問題。
• 確定性圖靈機多項式時間可驗證的問題。

證明概念：把一個多項式時間的驗證器(verifiers)轉成非決定性多項式時間圖靈機，反之亦然。

[舉例1] 分團問題

$CLIQUE = \{\ <G, k>\ |\ G 是一個有 k-clique的無向圖\  \}$

分團問題 (Clique problem) 是問一個圖中是否有大小是k以上的團。任意挑出k個點，我們可以簡單的在多項式時間內驗證(verify)出這k個點是不是一個團，所以這個問題屬於NP。

• 團 (clique) : 一個無向圖中，滿足兩兩之間有邊連接的頂點的集合
• k-團 (k-clique) : k個節點所形成的團

[舉例2] 子集合加總問題

$SUBSET_{SUM} = \{\ <S,t>\ |\ S = \{ x_1,..., x_k \} ，$ 

$再給定\{ y_1,...,y_l \}包含於 \{ x_1,...,x_k \}，有 y的總和為t \}$

子集合加總問題是從給定的一堆整數中挑一些整數加起來，看是不是目標數。而我們可以任意挑出k個數字，不知道對不對就直接全部試試看，並在多項式時間內驗證完畢，所以這個問題屬於NP。

References

Wiki - NP困難
https://zh.wikipedia.org/wiki/NP%E5%9B%B0%E9%9A%BE

Wiki - P (複雜度)
https://zh.wikipedia.org/wiki/P_(%E8%A4%87%E9%9B%9C%E5%BA%A6)

Wiki - NP (複雜度)
https://zh.wikipedia.org/wiki/NP_(%E8%A4%87%E9%9B%9C%E5%BA%A6)