Week 16 - HackMD

# Week 16 :::info :::spoiler Click to Open TOC [TOC] ::: # Question :::info :::spoiler Click to Open Question ![](https://i.imgur.com/vlF5qh1.png) ## Check - [ ] Q1 - [ ] Q2 - [ ] Q3 - [ ] Q4 - [ ] Q5 - [ ] Q6 - [ ] Q7 ::: # Answer ## Q1 > - [name=LXS] :::spoiler **【題目】** Show that any comparison-based algorithm needs $\Omega(nlogn)$ time to solve the following problem: Given n points in the 2D plane, construct a tree of minimum total length whose vertices are the given points and the edge length of an edge is the Euclidean distance between the two end points of the edge. ::: #### 【解題思路】首先 reduce sorting 問題到 EMST(euclidean minimum spanning tree) 問題。假如sorting問題的輸入是x1, x2, x3,...，存在一個對應的EMST問題，其中每個點的座標是(x1,x1), (x2,x2), ... ，每個輸入重複兩次，轉換的時間只要$O(n)$，EMST的答案中樹的兩端點是最大端與最小端，從隨意一端開始輸出，$O(n)$的時間可以轉回sorting的答案，基於比較的排序演算法下界$\Omega(nlogn)$，所以我們可以說，任何基於排序的演算法要$\Omega(nlogn)時間解決EMST$。  ## Q2 > - [name=chung] :::spoiler **【題目】** Show that if an algorithm makes at most a constant number of calls to polynomial-time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial time. Also show that a polynomial number of calls to polynomial-time subrountines may result in an exponential-time algorithm ::: #### 【Part1】【題目說明】在⼀個演算法中，呼叫常數次subroutines（Polynomial time），此外subroutines間的input與output互相牽動著，則其演算法時間複雜度也為 polynomial time 【證明】 :::spoiler **【原寫法】** 運用數學歸納法證明，假設呼叫n次subroutines，當n=1時，total time is polynomial成立假設當n=k時，total time is polynomial成立 Consider n = k+1, k+1次subroutines的total time = 呼叫k次subroutines的total time + 呼叫1次subroutines的total time = polynomial time + polynomial time(根據上述假設) = polynomial time 因此n=k+1時，total time is polynomial亦成立，故得證 ::: 假設子程式總共有 $y$ 個，其中複雜度最高為 $O(n^k)$ 多做的事情複雜度為 $O(n^d)$ 則子程式們總複雜度最多為 $O(n^{yk})$ 加上多做的事情，複雜度仍為 $O(n^{yk+d})$ 因為 $y, k, d$ 為常數，所以這還是 polynomial #### 【Part2】【題目說明】若呼叫polynomial次subroutines，則時間複雜度可能變為exponential-time 【證明】假設 $f(n) = 2^n$ ``` cpp= g(a){ int sum = 0; for i = 1 to a: sum = sum + i; } ``` $則f(n)\ is\ O(n)，g(a)\ is\ O(a)\\ g(f(n))=g(2^n)\ is\ O(2^n)為exponential$ 故呼叫polynomial次subroutines，時間複雜度可能變為exponential time，得證 ## Q3 > - [name=LXS] :::spoiler **【題目】** Show that the class P, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if $L1, L2\in P$, then $𝐿1\cup 𝐿2\in P$, $L1\cap L2\in P$, $L1L2\in P$, $\overline{𝐿1} \in P$, and $L1^* \in P$. ::: #### Union 聯集 $𝐿1, 𝐿2\in P \to 𝐿1, 𝐿2$可以被機器$M1, M2$在多項式時間$O(n^{k1}), O(n^{k2})$內決定，設計一台機器$M3$輸入為$x$，用以決定$L1\cup L2$，分別對$M1, M2$輸入$x$，如果$M1$或$M2$被接受時接受，否則拒絕。最糟情況下$M3$的時間複雜度為$O(n^{k1})+O(n^{k2})\in O(n^{max(k1, k2)})=O(n^{k3})$ 得出$M3$的語言也就是$𝐿1\cup 𝐿2\in P$ #### Intersection 交集前提假設同上，設計一台機器$M3$輸入為$x$，只在$M1, M2$都被接受時接受，否則拒絕。最糟情況下$M3$的時間複雜度為$O(n^{k1})+O(n^{k2})\in O(n^{max(k1, k2)})=O(n^{k3})$ 得出$M3$的語言也就是$L1 \cap L2 ∈ P$ #### Concatenation 前提假設同上，設計一台機器$M3$輸入為$x=a_1...a_n$ $\text{for i=0 to n:}$ 對於$M1$輸入$a_1...a_i$，對$M2$輸入$a_{i+1}...a_n$，當$M1, M2$接受則接受。 ```python= def M3(): for i in range(0,n): if M1(1,...,i) and M2(i,...,n): return True # Accept return False # Reject ``` 若for迴圈中沒有$i$使$M3$接受，則拒絕。時間複雜度為$O(n^{max(k_1,k_2)+1})\in P$ #### Complement 補集設計一台$M3$輸入為$x$，對$M1$輸入$x$，若$M1$拒絕則輸出接受，反之拒絕，反轉輸出時間仍為$O(n^{k1})$，得$\overline{𝐿1} \in P$。 #### Kleene star ```python= def M2(x): n = len(x) # dp[n]: x1...xn in L1* dp = [True, False for _ in range(1,n)] # dp[0] = True -> Empty set for i from 1 to n: for j from 0 to i: # x1 = x[0:j] x2 = x[j+1:i] # xj+1...xi if dp[j] and M1(x2): dp[i] = True return dp[n] ``` 時間複雜度為: $O(n)\cdot O(n)\cdot O(n^k) = O(n^{k+2})$ 得$L1^*\in P$ ## Q4 > - [name=xian] :::spoiler **【題目】** Show that if HAM-CYCLE ∈ P, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable. (Note 1: HAM-CYCLE is defined as "Does a graph G have a Hamiltonian cycle?") (Note 2: "HAM-CYCLE ∈ P" means that HAM-CYCLE is polynomial-time solvable.) ::: $\;$ 【解題思路】 Hamiltonian cycle定義為存在一個環包含所有頂點，且每個頂點只能被走過一次 $\rightarrow$ 因為已知 HAM-CYCLE ∈ P，因此我們可以利用此演算法解題。 1. 隨機選擇點 u，遍歷所有鄰邊，依序將鄰邊拿掉，並做 HAM-CYCLE 判斷此圖是否還存在 hamiltonian cycle。 2. 如果存在，則代表 ~~此邊~~ 不是我們要的，刪掉。 3. 如果不存在，則代表此邊 (u,v) 為hamiltonian cycle的其中一個邊。 4. 將 u 改成 v 重複執行 1~4，直到所有點皆被走過，且找到走回 u 的邊。【蘇都扣】 ```cpp= //假設G存在hamiltonian cycle list_ham_cycle(G){ random choose a vertex u t = u S = {u} while G.edge is not empty: for v in adj[t]: if v is visited G = G - e(t,v) break G* = G - e(t, v) if HAM-CYCLE(G*) G = G* else S.push(v) mark v as visited t = v return G, S } //最後的G為hamiltonian cycle, S 為 vertex ``` 【結論】 HAM-CYCLE ∈ P，假設 HAM-CYCLE = $O(n^k), n = |V|$ 1. 遍歷所有邊，並判斷 HAM-CYCLE $\rightarrow O(E·n^k)$ 2. 因為 E 最多 $n^2$，$O(E·n^k) = O(n^{2+k})$ 所以此題為 $polynomial-time\ solvable_\#$ ## Q5 > - [name=yee] :::spoiler 題目 Show that the Hamiltonian-path problem can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem. ::: 【解題思路】題目要在DAG中找到Hamiltonian-path，將topological sort 中While迴圈的條件改成若Q不等於1就停止，代表有超過兩個點的in degree等於0，所以找不到Hamiltonian-path。【蘇都扣】 ```cpp= Hamiltonian-path(G){ compute id[v] for each vertex v; for each v do if id[v] == 0 put v in Q; while Q.size == 1 do remove a vertex v from Q output v for each u in N(v)do if --id[u] == 0 put u in Q counter ++ if counter == n return } ``` 【時間複雜度】 $O(|V| + |E|)$ ## Q6 > - [name=Mark] :::spoiler 題目 Consider the language GRAPH-ISOMORPHISM = {<𝐺1, 𝐺2> : 𝐺1 and 𝐺2 are isomorphic graph}. Prove that GRAPH-ISOMORPHISM ∊ NP by describing a polynomial-time algorithm to verify the language. ::: **映射函數 f**題目提供的，根據助教課的解釋，我們假設已有映射函數的情況下找出Polynomial-Time的解法驗證兩個G是否為同構。 **蘇都扣** ```cpp= isomorphism(G1, G2) { //vertex數量不同 -> false if(G1.vertex_num != G2.vertex_num) return false //edge數量不同 -> false if(G1.Edges_num != G2.Edges_num) return false for each vertex V in G1 for each edge E in V if( G2.find(V).edge != E) //find()就是題目所供 return false; return true } ``` **Time Complexity** $O(VE)$ 對每個V檢查各自的邊，透過假設的映射函數find()檢查兩圖是否同構  ## Q7 > - [name=songchiu] :::spoiler 題目 Consider the problem of finding the longest simple cycle in an undirected graph. Give a related decision problem.Show the decision problem is an NP problem. ::: 先說明一下 `decision problem` 的意思是可否找到答案，yes or no ($1 \text{ or } 0$) 假設有一圖$G(V,E)$，我們要在裡面找到一條$\text{longest simple cycle}$，稱之為$\text{certificate}$，其點依序為$v_1, v_2, v_3,..., v_k$ 為確保該$\text{certificate}$是否為$\text{cycle}$，從$v_1$開始走，檢查$v_i v_{i+1}$是否在$G$裡。最後檢查完後如果都在$G$裡，就回傳$1$；反之則回傳$0$ (註：每個點只會被走過一次) 由於每個點只會被走訪一次因此我們可以推論出 $\text{longest simple cycle decision problem} \in NP$  參考連結：[certificate](https://www.geeksforgeeks.org/optimized-longest-path-is-np-complete/)