NiNi's Den

Advance-Algorithm::homework7

Words: 1,935Reading time: 10 min
2018/01/15 Share

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

1. 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.

  • page 4 - Problem 2-a
  • Kleene star
    2. 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 http://www.cs.wustl.edu/~pless/441/hw3soln.pdf

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

類似1.

4. 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$

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

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

stackoverflow
演算法筆記

↑這個方法太神啦

太屌辣

6. 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
7. 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
8. 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
9. 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

10. 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
11. 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.

隔天要考就沒寫了系列 呵呵

12. 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$.

這個好證,跟前面類似

13. 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.

這也好證

14. 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. 1. 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.
  2. 2. 2. Show that if the decision version of the Hamiltonian cycle is polynomial-time solvable then so is the problem of finding a Hamiltonian cycle.
  3. 3. 3. Show that the class $NP$, viewed as a set of languages is closed under union, intersection, concatenation and Kleene star.
  4. 4. 4. Prove that P $\subseteq$ NP$\cap$ co-NP and if NP$\ne$ co-NP,then P$\ne $NP.
  5. 5. 5. Show that 2-CNF-SAT is polynomial time solvable.
  6. 6. 6. 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.
  7. 7. 7. 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.
  8. 8. 8. 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.
  9. 9. 9. 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$.
  10. 10. 10. Show that the path cover problem is NP-complete.
  11. 11. 11. List all NP-complete problems (and give proofs) that appear in Ex.1~6.
  12. 12. 12. 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$.
  13. 13. 13. 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.
  14. 14. 14. Given an undirecter graph $G$ and a number $k$ :
  15. 15. a) Is there a cycle of length $\geq$ k?
  16. 16. b) Is there a cycle of length $\leq$ k?
  17. 17. c) Is there a spanning tree with each node of degree $\leq$ 3?