NiNi's Den

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.

(證明：連結裡面有)

## 題三

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

## 題四

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

↑這個方法太神啦

## 題六

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 同構

(以下簡稱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$

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$

(以下簡稱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顏色皆不同

(以下簡稱3SAT3CP)

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

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

## 題十

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$ 的任意元素(路徑)上

(以下簡稱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