NiNi's Den

Advance-Algorithm::homework7

Word count: 1.9kReading time: 9 min
2018/01/15 Share

建議如果看不懂算法的話可以拿起紙筆操作,因為我有點懶不想要畫圖。
感恩彬智讚嘆彬智

題一

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, $L1 \cup L2 \in P$,etc.


題二

Show that if the decision version of the Hamiltonian cycle is polynomial-time solvable then so is the problem of finding a Hamiltonian cycle.


題目:if Decision Hamiltonian Cycle(DHC) $\in P
\rightarrow$ Finding Hamiltonian Cycle(FHC) $\in P$

假設現在有一個演算法HamCycle(G)可以在P時間內解掉DHC
則我們可以建構以下演算法在確定性P時間內解掉FHC
(證明:連結裡面有)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
HCVertices(G)
H = []
next ← 0 // 初始值不重要
choose a starting node v
while G has unchecked edges do
if HamCycle(G) then
// 試著一個個拔掉連在v上的邊
// 如果有一個邊e被拿掉後,新的圖就不存在HC,那e就是HC的一部分
for all edges e = (v,u) on v do
G' ← G − e
if HamCycle(G') then
G = G'
else
add v to H
mark e as checked
next ← u
v ← next
return H

問題變轉(Problem Reduction)

媽我找到答案了 裡面的problem 1

題三

Show that the class $NP$, viewed as a set of languages is closed under union, intersection, concatenation and Kleene star.


類似1.

題四

Prove that P $\subseteq$ NP$\cap$ co-NP and if NP$\ne$ co-NP,then P$\ne $NP.


錦文的講義
$P \subseteq (NP \ \cap \ coNP) \rightarrow P \subseteq NP, P \subseteq coNP$
so if $P = NP \\
\rightarrow NP \subseteq (NP \ \cap \ coNP) \\
\rightarrow NP \subseteq coNP \ 又 \ size(NP)=size(coNP) \\
\rightarrow NP = coNP$

$\because P \Rightarrow Q$ 等價於 $\bar Q \Rightarrow \bar P$
$\therefore$ if $NP \neq coNP$, then $P \neq NP$

題五

Show that 2-CNF-SAT is polynomial time solvable.


CNF : conjunctive normal form,數位電路中的product of sum,例:$(A \lor B) \land (C \lor D)$

stackoverflow
演算法筆記

↑這個方法太神啦

太屌辣

題六

The subgraph isomorphism problem takes two graphs $G1$ and $G2$ and asks whether $G1$ is isomorphic to a subgraph of $G2$. Show that this problem is NP-complete.


Chegg標準解答

  • Subgraph Isomorphism Problem
    • Input :graph $G_1$, $G_2$
    • Output:$G_1$ 是否與 $G_2$ 的其中一個 subgraph 同構

證明 Clique Problem $\propto$ Subgraph Isomorphism Problem
(以下簡稱CPSIP)

  1. 已知 CP $\in$ NPC
    • Input :graph $S$, int $k$
    • Output:$S$ 是否存在一個 $k$-vertice 的完全子圖
  2. 輸入變轉:
    • SIP的輸入 $G_1 = k$-clique:$O(N^2)$
    • SIP的輸入 $G_2 = S$:$O(N^2)$
  3. 因為CP(S,k) = SIP(k-clique,S)
  4. 所以 CP $\propto$ SIP $\rightarrow$ SIP $\in$ NP-hard
  5. SIP $\in$ NP(簡單寫個NP演算法就知道了)
  6. SIP $\in$ NPC

題七

Given an integer m-by-n matrix $A$, and an integer m-vector $b$, the integer programming problem asks whether there is an integer n-vector $x$ such that $Ax \leq b$. Prove that this problem is NP-complete.


  • Integer Programming Problem
    • Input :m*n matrix $A$, m-vector $b$
    • Output:是否存在一 n-vector $x$ 使得 $Ax \leq b$

證明 SAT $\propto$ Integer Programming Problem (IPP)

  1. 已知 SAT $\in$ NPC

    • Input :CNF布林函式 $E(x) = C_1 \land C_2 \land … \land C_k$ , $x = { x_1,…,x_n}$
      如 $C_1 = \lnot x_1 + x_3 + x_7$
    • Output:是否存在一組輸入當作 $x$ 使得 $E(x) = True$
  2. 變轉:

    • IPP的輸入$A = \begin{bmatrix}a_{11} & a_{12} & … & a_{1n} \\
      … & … & … & … \\
      a_{m1} & a_{m2} & … & a_{mn} \\
      \end{bmatrix}$, $b = \begin{bmatrix}b_1 \\
      … \\
      b_m \\
      \end{bmatrix}$, 其中各列 $a_i*b$ 對應到 $C_i$

    • 如:$C_1$ 對應 $(1-x_1)+x_3+x_7 \geq 1 \\
      \rightarrow -x_1+x_3+x_7 \geq 0 \\
      \rightarrow x_1-x_3-x_7 \leq 0 \\
      \rightarrow a_1 = {1,0,-1,0,0,0,-1,…}, b_1=0$

    • IPP的輸出改為:是否存在一 n-vector $x={0,1}$ 使得 $ A_x \leq b$,0 對應 $False$,1 對應 $True$

  3. 因為SAT(E) = IPP(A,b)

  4. 所以 SAT $\propto$ IPP $\rightarrow$ IPP $\in$ NP-hard

  5. IPP $\in$ NP(簡單寫個NP演算法就知道了)

  6. IPP $\in$ NPC

題八

Given a set $S$ of integers, determine whether there exists a subset $A \subseteq S$, such that $\sum_{x\in A}x = \sum_{x\in S-A} x$. Show this problem is NP-complete.


Problem 1

  • Partition Problem
    • Input :set $S$
    • Output:是否存在 $S_1, S_2 \in S, S_1 \cap S_2 = \varnothing$ s.t. $\sum S_1 = \sum S_2$

證明 Subset Sum Problem $\propto$ Partition Problem
(以下簡稱SSPPP)

  1. 已知 SSP $\in$ NPC
    • Input :set $S$, int $k$
    • Output:是否存在 $S’ \in S$ s.t. $\sum S’ = k$
  2. 變轉:
    • PP的輸入 $X = S \cup {s-2k}$, $s = \sum S$
  3. 因為SSP(S,k) = PP(X)
    • 若左則右:若SSP(S,k)成立,代表$S$中有subset $S’$ 加總為 $k$,則在PP(X)中就可以將 $X$ 分為 $S’\cup {s-2k}$ 和剩下的一半,加總皆為 $s-k$
    • 若右則左:若PP(X)成立,代表互斥子集 $S_1, S_2$ 加總皆為 $s-k$,且必定其中一邊含有 $s-2k$,將其去除後,該集合 $S’$ 加總為 $k$ 且 $S’ \in S$
  4. 所以 SSP $\propto$ PP $\rightarrow$ PP $\in$ NP-hard
  5. PP $\in$ NP(簡單寫個NP演算法就知道了)
  6. PP $\in$ NPC

題九

An undirected graph $G$ is k-colorable, if we can color $V(G)$ using at most $k$ colors such that for each edge $xy$ in $E(G)$, its two end vertices are $x$ and $y$ are colored with different colors. Let k-COLOR denote the problem of determine whether $G$ is k-colorable. Show that k-COLOR is NP-complete for any constant $k \geq 3$.


3SAT $\propto$ 3著色 $\propto$ k著色

  • k Coloring Problem

    • Input :graph $G$, int k , $k > 2$
    • Output:是否存在一種最多使用k色的著色方式,使G上相鄰的vertex顏色皆不同
  • 3 Coloring Problem

    • Input :graph $G$
    • Output:是否存在一種最多使用3色的著色方式,使G上相鄰的vertex顏色皆不同

證明 3SAT $\propto$ 3 Coloring Problem
(以下簡稱3SAT3CP)

  1. 已知 3SAT $\in$ NPC
    • Input : formula $\phi$variables Set $X$, clauses set $C$ 靠 突然不會訂輸入
    • Output : 是否能指定$X$一組布林值使$C$中的子句皆為真
  2. 變轉:
    • 3CP的輸入G = $G_{\phi}$

總之他把圖構成類似電路圖的樣子

然後如果要證明 3著色 $\propto$ k著色
其實非常簡單,以四色為例:

  • 四色的輸入為:我們只要在三色圖上面新增一個點,並且這個點跟其他所有的點都有邊
  • 四色的輸出為:是否存在一種著色方法,只用四色就可以畫這張圖
    假設原圖可以用3色著色,那剛才多加的那個點,一定會需要用到第四色,所以我們可以知道,要變轉到k色著色,只要幫3色圖的輸入加上k-3個點,且這幾個新增的點到每點都要有邊,這樣我們就可以證明 3著色 $\propto$ k著色了。

https://www.clear.rice.edu/comp487/3sat-to-3col.pdf
https://cgi.csc.liv.ac.uk/~igor/COMP309/3CP.pdf

題十

Show that the path cover problem is NP-complete.


  • Path Cover Problem
    • Input :graph $G’$, int k
    • Output:是否存在一個path的集合 $S$, $|S|<k$, s.t. 所有點都在 $S$ 的任意元素(路徑)上

證明 Hamiltonian Cycle Problem $\propto$ Path Cover Problem
(以下簡稱HCPPCP)

  1. 已知 HCP $\in$ NPC
    • Input :graph $G$
    • Output:是否存在一cycle $c$ s.t. 所有點都恰在 $c$ 上出現一次
  2. 變轉:
    • PCP的輸入 $G’ =$ 在原圖 $G$ 上找一個邊$(u,v)$,並在 $u$ 上接上一個新的點 $u’$,在 $v$ 上接上一個新的點 $v’$,形成的新圖當作$G’$
    • PCP的輸入 $k = 1$
  3. 所以 HCP $\propto$ PCP $\rightarrow$ PCP $\in$ NP-hard
  4. PCP $\in$ NP(簡單寫個NP演算法就知道了)
  5. PCP $\in$ NPC

題十一

List all NP-complete problems (and give proofs) that appear in Ex.1~6.


Determine whether each of the following problems is polynomial time solvable or NP-complete.

應該不會考吧
隔天要考就沒寫了系列 呵呵

題十二

Given a set $S$ of $n$ real numbers, another real number $M$, and an integer $k$, we want to determine whether or not there exist $k$ elements in $S$ whose sum is exactly $M$.


這個好證,跟前面類似

題十三

We are given an integer $k$ and $n$ objects which have to be placed in bins of equal capacity $M$. Object $i, 1 \leq i \leq n$, requires mi units of capacity. The objective is to determine whether $k$ bins are enough to accommodate all $n$ objects. No object may be placed partly in one bin and partly in another.


這也好證

題十四

Given an undirecter graph $G$ and a number $k$ :
a) Is there a cycle of length $\geq$ k?
b) Is there a cycle of length $\leq$ k?
c) Is there a spanning tree with each node of degree $\leq$ 3?


應該還可以

Original Author: Terrynini

Original link: http://blog.terrynini.tw/tw/Advance-Algorithm-homework7/

Publish at: January 15th 2018, 12:23:37

Copyright: This article is licensed under CC BY-NC 4.0

CATALOG
  1. 1. 題一
  2. 2. 題二
  3. 3. 題三
  4. 4. 題四
  5. 5. 題五
  6. 6. 題六
  7. 7. 題七
  8. 8. 題八
  9. 9. 題九
  10. 10. 題十
  11. 11. 題十一
  12. 12. 題十二
  13. 13. 題十三
  14. 14. 題十四