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 清

• NP 並非搜集不能在 polynomial time 解決的問題，而是搜集可以在nondeterministic polynomial time 解決的問題

105 交 59

• NP 的 polynomial time algorithm 需要 certificate

106 交

• 如果 A 是 NP problem，則必定存在一個 NP algorithm B 可以解 A

103 成

• 如果 P = NP，則 NP = NPC

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 例子：

circuit SAT

Given 一個bool combinatorial circuit，是否能找到一種 assign 的方式使 output = 1

circuit SAT 的 complement problem

Given 一個bool combinatorial circuit，是否給任何 input 都會使 output = 0

• if NP
  $\ne$ co-NP, then P
  $\ne$ NP

coNP-complete

coNP 中最難的問題

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

• P ⊆ NP（易解的必為易驗證的）
• NPC ⊆ NP
• P ⊆ co-NP

更詳細的 NPC 筆記

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 交

• 任何 NP-hard problem 都可以 polynomial reduce 到任何 NPC problem（錯！）
• 如果存在某個
  $\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
  $O(n!)$

110 台

• 由此例可見並非所有 NP problem 都可以 solved in exponential time
  101 交
  「 給一個 graph，問是否存在 min-degree spanning tree ，其 max degree 為 2」等同 Hamiltonian Path

min-degree spanning tree 即取 spanning tree 其 max degree 是最小的

$\to$ 如果 spanning tree 的 max degree 是 2，則它是 Hamiltonian Path

• 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
  $O(2^n)$

給一個 bool 組合電路，能不能找到一種 assign 的方式使 output = 1

• SAT
• 3-CNF-SAT

$\to$ 3-CNF-SAT 中每個 clause 必須恰好有三個 literals

$\to$ SAT 和 3-CNF-SAT 的差別在於 SAT 不一定要恰好三個 literals

$\to$ 對於任何長度大於 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

$\to$ formula 具 k 個 clause
因為是 3-CNF 所以每個 clause 要恰好有三個相異的 literals

$\to$ 只要在不同的 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 是一個

$setS$，

$S$ 包含許多數字，set partition 是問能否將

$S$ 分成

$A$ 和

$S-A$ 使

$A$ 裡所有元素和

$=S-A$ 裡所有元素和

• independent set

在一個 graph 裡找最大的 independent set

independent set 是一個 graph

$G=(V,E)$ 中

$V$ 的 subset

$V^{\prime }$ 使得對所有

$e\in E$，

$e$ 最多只有一個點在

$V^{\prime }$ 中

• longest path

101 交
「給一個無向圖和一個正整數 k，如果所有邊的長度都是 1 ，且每個點最多只能走一次，問是否有 path 長度至少是 k」等同問 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
  $$
  $O(n^2)$
  
  $\leftrightarrow$ 是否 2-colorable

用 BFS / DFS

adjacency list:

$O(V+E)$
adjacency matrix:

$O(V^2)$