Week 16

Click to Open TOC

• Week 16
• Question
• Answer
  • Q1
    • 【解題思路】
  • Q2
    • 【Part1】
    • 【Part2】
  • Q3
    • Union 聯集
    • Intersection 交集
    • Concatenation
    • Complement 補集
    • Kleene star
  • Q4
  • Q5
  • Q6
  • Q7

Question

Click to Open Question

Check

• Q1
• Q2
• Q3
• Q4
• Q5
• Q6
• Q7

Answer

Q1

• LXS

【題目】

Show that any comparison-based algorithm needs

$\mathrm{\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的答案，基於比較的排序演算法下界

$\mathrm{\Omega }(nlogn)$，所以我們可以說，任何基於排序的演算法要

$\mathrm{\Omega }(nlogn)\mathrm{時}\mathrm{間}\mathrm{解}\mathrm{決}EMST$。

Q2

• chung

【題目】

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

【證明】

【原寫法】

運用數學歸納法證明，假設呼叫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$

g(a){
    int sum = 0;
    for i = 1 to a:
        sum = sum + i;
}

$$\begin{gathered} \mathrm{則}f(n)isO(n)，g(a)isO(a) \\ g(f(n))=g(2^n)isO(2^n)\mathrm{為}exponential \end{gathered}$$
故呼叫polynomial次subroutines，時間複雜度可能變為exponential time，得證

Q3

• LXS

【題目】

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

$L{1}^{\ast }\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\in 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$接受則接受。

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

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})$
得

$L{1}^{\ast }\in P$

Q4

• xian

【題目】

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定義為存在一個環包含所有頂點，且每個頂點只能被走過一次

$\to$ 因為已知 HAM-CYCLE ∈ P，因此我們可以利用此演算法解題。

1. 隨機選擇點 u，遍歷所有鄰邊，依序將鄰邊拿掉，並做 HAM-CYCLE 判斷此圖是否還存在 hamiltonian cycle。
2. 如果存在，則代表 此邊 不是我們要的，刪掉。
3. 如果不存在，則代表此邊 (u,v) 為hamiltonian cycle的其中一個邊。
4. 將 u 改成 v 重複執行 1~4，直到所有點皆被走過，且找到走回 u 的邊。

【蘇都扣】

//假設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
   $\to O(E·n^k)$
2. 因為 E 最多
   $n^2$，
   $O(E·n^k)=O(n^{2+k})$

所以此題為

$polynomial-timesolvabl{e}_{\mathrm{\#}}$

Q5

• yee

題目

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。

【蘇都扣】

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

• Mark

題目

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是否為同構。
蘇都扣

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

• songchiu

題目

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