# Week 17

:::info
:::spoiler Click to Open TOC
[TOC]
:::

# Question
:::info
:::spoiler Click to Open Question

## Check
- [x] Q1
- [ ] Q2
- [ ] Q3
- [ ] Q4
:::

# Answer
## Q1
> - [name=LXS]

:::spoiler 題目
Let 2-CNF-SAT be the set of satisfiable Boolean formula in CNF with exactly 2 literals per clause. Show that 2-CNF-SAT ∈ P. Make your algorithm as efficient as possible. (Hint: Observe that x ∨ y is equivalent to ¬x → y. Reduce 2-CNF-SAT to an efficiently solvable problem on a directed graph.)
:::

#### 【解題思路】
將一個Boolean formula，其中有n個Boolean variable、m個calause，轉成一個directed graph，每個Boolean variable，$x_1,...,x_n$對應圖中點 $x_1,\neg x_1,...,x_n,\neg x_n$ 共2n個點，每個calause $x\lor y$相當於$\neg x\to y\land \neg y\to x$，對於圖中我們也連接$\neg x\to y$與$\neg y\to x$共個點共2m個邊。

首先找strongly connected components，需要$O(n)$時間，然後確保每個$x_k$與$\neg x_k$不在同一個SCC(不能存在$x_k\to ...\to\neg x_k$，$\neg x_k\to ...\to x_k$)，需要$O(n)$，如果在同一個S CC則該Boolean formula是Unsatisfiable的。

我們可以在多項式時間內決定2-CNF-SAT問題，因此2-CNF-SAT ∈ P.

#### 找Assignment

假如我們把每個SCC視為一個點(同一個SCC塗同樣顏色)稱作$G$，將每個點之間的邊的方向相反，稱作$G^T$，在$G^T$中，依照從原本$G$的Sink開始按照拓撲排序填色，相連的兩個SCC中填入相反的顏色，否則填入相同顏色，將同Sink顏色的點設為true即可以找到assignment。

## Q2
> - [name=xian]

:::spoiler **【題目】**
The subgraph-isomorphism problem takes two undirected graphs G1 and G2, and it asks whether G1 is isomorphic to a subgraph of G2. Show that the subgraph-isomorphism problem is NP-complete.
:::

【證明】
> 證明 $SIP\in NP \rightarrow 驗證 \in P$

* 假設我們有G1和G2的子圖G，從上禮拜作業已證明 GRAPH-ISOMORPHISM $\in NP$，證明同構需要驗證以下四項：
1. Equal number of vertices.
2. Equal number of edges
3. Same degree sequence
4. Same number of circuit of particular length
* 而這些都可以在 $P$ 時間內驗證
* 因此 $SIP \in NP$

> 證明 $SIP\in \text{NP-hard} \Rightarrow \text{CLIQUE} \le_p SIP$

* $對於\text{CLIQUE}問題給定一張圖G_2，另外生成一圖G_1，令G_1=K_i，|G_1|=i的完全圖， i\le |G_2|$，問$G_2$是否存在一個大小為 $k$ 的完全子圖(cliqu) $G$
* $如果G_2存在大小為i的\text{CLIQUE}，則G_1為G_2的子圖$
* 因此將$G_1、G_2$ 丟入 $SIP$ 中，確認 $G_1$ 是否和 $G_2的子圖$同構
* 如果同構則回答true，不同構則回答false

$\because 生成\ G_1\ 最多只需\ O(|G_1|^2)，因此轉換時間為指數時間$
$\therefore \text{CLIQUE}$在指數時間下可解，則$SIP$也可
且我們已知$\;\text{CLIQUE} \in \text{NP-hard}\ \land SIP \in NP \implies SIP \in \text{NP-hard}$

又因為 $SIP \in \text{NP-hard}\ \land NP$
$\therefore\ \bf SIP \in \text{NP-complete}_\#$

## Q3
> - [name=chung]
:::spoiler **【題目】**
Given an integer m x n matrix A, and an integer m-vector b, the 0-1 integer-programming problem asks whether there exists an integer n-vector x with elements in the set {0, 1} such that Ax ≤ b. Prove that 0-1 integer programming problem is NP-complete. (Hint: Reduce from 3-CNF-SAT.)
:::

**【證明】**
- Problem ∈ NP : Find a certificate to verify that it is the correct answer to this question.
- A certificate would be the n-vector x, and we can verify in polynomial time that Ax ≤ b, so 0-1 integer linear programming (01LP) is in NP.

- Problem ∈ NP-hard : 3-CNF-SAT $≤_𝑝$ 0-1 integer- programming problem
- 3-CNF-SAT
$Ex : ( 𝑥_1∨𝑥_2∨𝑥_3 ) ∧ ( 𝑥_1∨¬𝑥_3∨¬𝑥_4 )$
If $𝑥_𝑗$ in clause i with negation → $𝐴_(𝑖,𝑗) = 1$
If $𝑥_𝑗$ in clause i without negation → $𝐴_(𝑖,𝑗) = -1$
Other, $𝐴_(𝑖,𝑗) =0$
$𝑏_𝑖$ = – 1 + num of negation in clause i
$( 𝑥_1∨𝑥_2∨𝑥_3 ) : 𝑥_1+𝑥_2+𝑥_3≥1 ⇒ −𝑥_1−𝑥_2−𝑥_3≤−1 \\
( 𝑥_1∨¬𝑥_3∨¬𝑥_4) : 𝑥_1+(1−𝑥_3 )+(1−𝑥_4)≥1 ⇒ −𝑥_1+𝑥_3+𝑥_4≤1 \\
Ax ≤ b : \begin{bmatrix} -1&-1&-1&0\\-1&0&1&1 \end{bmatrix}𝜒 ≤ \begin{bmatrix} -1\\1 \end{bmatrix}$
轉換時間在 polynomial time 內，其又為 NP Problem，故得證 0-1 integer- programming problem is NP-complete.

## Q4
> - [name=yee]
:::spoiler **【題目】**
Based on hw14-7,we know that longest-simple-cycle problem is an NP-problem.
Prove that the problem is NP-complete
:::

**【解題思路】**
由14-7我們知道LSC為NP問題，$\text{certificate}$依序為$v_1, v_2, v_3,..., v_k$，且已知Hami-cycle 為NP-complete問題，因此可由Hami-cycle reduce to LSC 來證明LSC也是NP-complete問題。

**【證明】**

$Hami-cycle <=_p LSC$

若一Graph存在一個Hami-cycle也代表該Graph存在一k = |V|的LSC，若一Graph存在一序列$v_1, v_2, v_3,..., v_n(n = |V|)$的LSC，也代表該Graph也存在一Hami-cycle，因此可知Hami-cycle\ \ iff.\ LSC
$\therefore\ \bf LSC \in \text{NP-complete}_\#$