---
title: Homework XV
---
# P1
[CLRS 3rd] Exercise 34.1-5
## Topic
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 subroutines may result in an exponential-time algorithm.
## Solution
### a.
若subroutine只call常數次,則時間複雜度最多為 $O( (((n^{d_1})^{d_2})\dots)^{d_m})$
達不到 $O(n^n)=O(2^{nlg(n)})\in$ exponential
所以加上additional work後還是
$O\left ( n^{d_1+d_2+\dots+d_m} + n^{c}\right )$ $\in$ polynomial time
### b.
假設n個subroutine都做時間複雜度為O(n)的運算使 $n\to n^2$
則 $sub_1:n=n$
$sub_2:n^2$
$sub_3:n^4$
$sub_4:n^8$
...
$sub_n:n^{2^{n-1}}$
所以時間複雜度會是 $O(n^{2^n})\in$ exponential

# P2
[CLRS 3rd] Exercise 34.1-6
## Topic
Show that the class P, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if $L_1,L_2$∈P, then $L_1​∪L_2$​∈P, $L_1∩L_2$∈P, $L_1L_2$∈P, $\bar L_1 \in P$, and$L_1^* \in P$
## Solution
union : $L_1​∪L_2$​∈P, polynomial time(return $L_1$ or $L_2$ )
intersection : $L_1∩L_2$∈P, polynomial time(return $L_1$ and $L_2$ )
concatenation : $L_1L_2$∈P, polynomial time(return True if ($L_1$ and $L_2$), else false )
complement : $\bar L_1 \in P$, polynomial time(return not $L_1$ )
Kleene star : $L_1^* \in P$, use dynamic programming,which is $n^3$, so it is polynomial time
### Example of kleene star

# P3
[CLRS 3rd] Exercise 34.2-3
- [ ] [name=Haneul]
## Topic
Show that if $HAM-CYCLE∈P$, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable.
## Solution
假設$HAM-CYCLE∈P$，我們可以用下面pseudocode的方法來找hamiltonian cycle，由於line.4處判斷是否為hamiltonian cycle花了polynomial time，因此符合題目所述的polynomial-time solvable

For all node v ∈ V:
    For each pair {e1,e2} ∈ Ev: //Ev 代表所有接著節點v的edge 
        construct graph G' = (V,(E-Ev)∪{e1,e2})
        if G' contains a hamiltonian cycle: //line.4
            record the pair of {e1,e2}
            break
    if no pair of Ev get recorded
        return false
print all recorded pairs in order
return true 

# P4
[CLRS 3rd] Exercise 34.2-7
## Topic
Show that the hamiltonian-path problem from Exercise 34.2-6 can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem.

==Exercise 34.2-6:==
A hamiltonian path in a graph is a simple path that visits every vertex exactly once. Show that the language $\text{HAM-PATH}$ ={⟨G,u,v⟩:= there is a hamiltonian path from u to v in graph G} belongs to $\text{NP}$.
## Solution
為了證明找到DAG上的HAM-PATH屬於$\text{NP}$, 要找到一個polynomial-time的驗證演算法
符合以下條件者為hamiltonian path:
1. 路徑為n個相異點 O(n)
2. 路徑中相鄰點在DAG裡有邊連結 O(n+m)
3. 路徑頭尾為u, v O(1)

在O(n+m)時間內可以驗證一條路徑是否為hamiltonian path, 因此找到DAG上的HAM-PATH屬於$\text{NP}$

# P5
[CLRS 3rd] Exercise 34.2-10
- [ ] [name=民]
## Topic
Prove that if NP≠co-NP, then P≠NP.
## Solution
假設 NP≠co-NP，讓 L ∈ NP\co-NP。因為P ⊂ NP ∩ co-NP 且 L ∉ NP ∩ co-NP，我們可得到 L ∉ P. 因此 P≠NP。
# P6
- [ ] [name=Joe]

[CLRS 3rd] Exercise 34.2-11
## Topic
Let G be a connected, undirected graph with at least 3 vertices, and let $G^3$ be the graph obtained by connecting all pairs of vertices that are connected by a path in G of length at most 3. Prove that $G^3$ is hamiltonian. (Hint: Construct a spanning tree for G, and use an inductive argument.)
## Solution
將G畫成spanning tree T，並將T中隨機一點v刪除，
這時T會因為斷點形成好幾個獨立的connected components，
依照這些connected components的大小分成三個部分討論。
PART1:size = 1
因為這些點到v的距離=1，所以到彼此的距離為2，根據定義$G^3$中的這些邊也有edge，所以可以把他們全部連在一起形成一個ham-cycle。
PART2:size = 2
假設x是和v連結的點，y是connected component中另一個點，
所以y到v的距離為2，根據定義$G^3$中y和v也相連，所以每個connected components都可以形成ham-cycle
PART3:size >= 3
根據size=2的結果，這些connected components中至少有兩點和v相連，又他們彼此間可以相連成為ham-cycle，所以同樣可以和v形成ham-cycle
因為這些ham-cycle都和v相連，彼此必定可以相連(距離<=3)，所以可以把這三個部份的connected components全部連成一個大的ham-cycle
因此$G^3$必定是ham-cycle
> 覺得有甚麼問題在跟我說一下[name=Joe][color=#f33]
> 再[name=Lin]
> 柏喬很棒[name=周]

# P7
[CLRS 3rd] Exercise 34.4-7
## Topic
Let $\text{2-CNF-SAT}$ be the set of satisfiable boolean formulas in $\text{CNF}$ with exactly 2 literals per clause. Show that $\text{2-CNF-SAT} \in P$. Make your algorithm as efficient as possible. (Hint: Observe that $x \vee y$ is equivalent to $\neg x \to y$. Reduce $\text{2-CNF-SAT}$ to an efficiently solvable problem on a directed graph.)
## Solution
(x $\wedge$ y)等價於 $\neg x \to y$, 一個括號的值若為true, 只有兩種可能:
1. $\neg x為true且y為true$
2. $\neg y為true且x為true$

所以為了讓CNF的值為true, 每個括號都要符合這個條件

若建立一個圖, 圖中的點是把所有括號裡的literals和他的相反值(x和$\neg x$), 邊是括號裡的literals決定的((x $\wedge$ y) 圖中就有$\neg x連到y$和$\neg y連到x$)
若有任何一個路徑的終點是自己的相反值(x到$\neg x$或相反), 則代表有一組布林值讓每個括號都是true, 因為每條邊都確定兩個布林值, 連成路徑代表布林值的一致性

對圖跑Floyd-Warshall algorithm$O(n^3)$可以確定點是否連通, 如果有一個路徑的終點是自己的相反值, 怎有答案, 找不到一條這樣的路徑則沒有答案