## Definition（概念版）

### NP

NP 就是收集那些容易驗證的問題
> 容易驗證：可在 polynomial time 內驗證

什麼叫做可以被驗證（verifiable）呢？
> Given a "certificate" of a solution, then we could verify that the certificate is correct in polynomial time

> 106 清
- <font color = "red">NP 並非搜集不能在 polynomial time 解決的問題</font>，而是搜集可以在nondeterministic polynomial time 解決的問題

> 105 交 59
- NP 的 polynomial time algorithm ++需要 certificate++

> 106 交
- 如果 A 是 NP problem，則必定存在一個 NP algorithm B 可以解 A

> 103 成
- <font color = "red">如果 P = NP，則 NP = NPC</font>

### coNP

> X $\in$ coNP
> $\leftrightarrow$ X's complement $\in$ NP

Wiki 解釋：
>While an NP problem asks whether a given instance is a yes-instance, its complement asks whether an instance is a no-instance, which means the complement is in co-NP.
>>Any yes-instance for the original NP problem becomes a no-instance for its complement, and vice versa.

complement problem 例子：

<font color = "snake">circuit SAT</font>
> Given 一個bool combinatorial circuit，是否能找到一種 assign 的方式使 output = 1

<font color = "snake">circuit SAT 的 complement problem</font>
> Given 一個bool combinatorial circuit，是否給任何 input 都會使 output = 0

- <font color = "red">if NP $\ne$ co-NP, then P $\ne$ NP</font>

### coNP-complete

> coNP 中最難的問題
- 如果能找到一個 polynomial time 的 algo 來解某個 co-NPC 的問題，所有的 co-NP problem 都 polynomial time 可解


* P ⊆ NP（易解的必為易驗證的）
* NPC ⊆ NP
* <font color="#f00">P ⊆ co-NP</font>

>更詳細的 [NPC 筆記](https://hackmd.io/MSS9o3W_Ra-62aRfGqxASQ)

### Polynomial Reduction

(如果 L1 可以 polynomial reduce 到 L2)
L2 易解保證 L1 易解
> $\le_p$ 的符號可以理解成 $\le$ 也就代表 L2 是比較難的


- if any ==NP-Complete== problem can be solved in polynomial time, then ++every++ problem in ==NP== has a polynomial time solution
> 105 交 60
- 任何 P 裡的問題都可以 polynomial reduce 到 SAT

### 是否為 NP-hard

> 105 交
- [ ] <font color="#f00">任何 NP-hard problem 都可以 polynomial reduce 到任何 NPC problem</font>（錯！）
- [x] 如果存在某個 $\in$ NPC 的 problem 可以 polynomial reduce 到另一個 problem A，則 A 是 NP-hard

---
## 常考分類判斷

### 【P】
- 2-CNF-SAT
- Euler circuit
> 

### 【NP】

- Hamiltonian Cycle

> 假設給一個 proposed solution {s,w,v,u,t} ，要檢查是否為 Hamiltonian Cycle ，只需確認起點是否等於終點（s = t?），經過的點之間是否真的都有邊即可（$(s,w), (w,v), (v,u), (u,t) \in E \ ?$）
>
> 離散補充：如果 G 是一個 undirected bipartite graph，且有奇數個點，G 就沒有 Hamiltonian Cycle

- Hamiltonian Path
- graph isomorphism
- integer factorization
> Given 正整數 m, n，m 是否有比 n 小且比 1 大的因數
> 105 交
> 如果 P=NP，我們就可以在 polynomial time 內 factorize 任何 integer
- maximum flow

### 【NPC】（所以也是 NP、NP-Hard）

推導架構圖：
- Hamiltonian Cycle / Path <font color = "red">$\quad O(n!)$</font>
> 110 台
> - 由此例可見並非所有 NP problem 都可以 solved in exponential time
> 101 交
> 「 <font color = "prince">給一個 graph，問是否存在 min-degree spanning tree ，其 max degree 為 2</font>」等同 Hamiltonian Path
>> min-degree spanning tree 即取 spanning tree 其 max degree 是最小的
>> $\rightarrow$ <font color = "red">如果 spanning tree 的 max degree 是 2，則它是 Hamiltonian Path</font>
- TSP
> 106 清
> if P $\ne$ NP, then $\nexists \ \rho$-approximation algorithm for TSP
>> $\rho$: arbitrary constant $\ge 1$
- longest simple cycle
> 在一個 graph 中找一個點不重複的最長 cycle
> 光是判斷一個 Graph 中有沒有長度為 k 的 simple path 就是 NP-complete
- circuit SAT <font color = "red">$\quad O(2^n)$</font>
> 給一個 bool 組合電路，能不能找到一種 assign 的方式使 output = 1
- SAT
- 3-CNF-SAT
> $\rightarrow$ 3-CNF-SAT 中每個 clause 必須恰好有三個 literals
> $\rightarrow$ SAT 和 3-CNF-SAT 的差別在於 SAT 不一定要恰好三個 literals
> $\rightarrow$ 對於任何長度大於 3 的 CNF boolean formula，我們都可以把它轉換成 3-CNF-SAT，前提是++要可以加額外的變數++
> 例子：
> 

> 105 交
> SAT 轉 3-SAT，轉換後 3-SAT Clause 中的 literals 不一定在SAT 中也來自同個 Clause

- clique
> clique: complete subgraph
> size of clique: clique 中有幾個 vertices
> 找最大的（含最多點的）complete subgraph
> 

> 3-CNF-SAT 轉 clique
> 要確認是否有 size = k 的 clique
> $\rightarrow$ formula 具 k 個 clause
> 因為是 3-CNF 所以每個 clause 要恰好有三個相異的 literals
> $\rightarrow$ 只要在不同的 clause 裡，且其中一個不為另一個的 negation 就建立相連的邊

- vertex cover
> 找一個 Graph 中最小的 vertex cover
> vertex cover 定義：
> ++a set of vertices that includes at least one endpoint of every edge of the graph++
>
> Note:
> graph G 有 $size = k$ 的 clique
> $\leftrightarrow$ G 的補圖中有 $size = |V| - k$ 的 vertex cover
>
> 

- 3-coloring (superpolynomial time: $O(1.3289^n)$)
- 4-coloring (superpolynomial time: $O(1.7272^n)$)

> superpolynomial time: 比所有 $O(n^k)$ 成長的都還要快（例如指數、階乘型）

- subgraph isomorphism
- 0-1 integer programming
- integer linear programming
- set partition
> input 是一個 $set \ S$，$S$ 包含許多數字，set partition 是問能否將 $S$ 分成 $A$ 和 $S-A$ 使 $A$ 裡所有元素和 $= S-A$ 裡所有元素和

- independent set
> 在一個 graph 裡找最大的 independent set
>> independent set 是一個 graph $G = (V,E)$ 中 $V$ 的 subset $V'$ 使得對所有 $e \in E$， $e$ 最多只有一個點在 $V'$ 中
- longest path
> 101 交
> 「<font color = "prince">給一個無向圖和一個正整數 k，如果所有邊的長度都是 1 ，且每個點最多只能走一次，問是否有 path 長度++至少++是 k</font>」等同問 longest path
- subset sum
> pseudo-polynomial time $O(nk)$
>> n: 數字總數，k: 所求的 sum 值
>> 用 DP

### 【NP-HARD】
- 每個 edge weight = 1
- **longest** simple path in digraph
- find a **largest** cycle
- **有負環**的 digraph 找一個 shortest simple path

### 【co-NP】
- integer factorization
- tautology

### 【co-NPC】
- Determining if a formula in propositional logic is a tautology

---
## 常考時間判斷

- 是否 bipartite $\qquad$ ==$O(n^2)$==
$\leftrightarrow$ 是否 2-colorable
> 用 BFS / DFS
>> adjacency list: $O(V + E)$
>> adjacency matrix: $O(V^2)$