### Definition

* NPC 是用在講一個 problem 有多難，而非有多簡單
* NPC 並非用在 opt problem（找出某個 optimal solution 的 problem)，而是用在 decision problem（判斷是 Y / N 的problem）

> 可以想像 decision problem 是一個 function，把 instance set I map 到 {0, 1}

---

通常我們要講一個 opt problem 是 hard 時，我們可以從它的 related decision problem 下手，因為 decision problem 通常比較簡單（至少不會比求 opt 難）

>例如：
>>一個 opt problem：
**shortest path**
它的 related decision problem：
**path**
*（給定一個 digraph G、 點 u, v、 int k ，是否存在一條 path 從 u 到 v，用至多 k 個 edges）*

從這個例子可以知道為什麼求解 decision problem 比 opt problem 容易：
>opt → decision
>>如果我們可以解從 u 到 v 的 shortest path，我們就可以在求得最短路徑後，再拿最短路徑長去跟 decision problem 的 k 做比較，即可知是否存在長度為 k 的 path。

如果 opt problem easy → decision problem 也 easy
如果 decision problem 就已經是 hard 了 → opt problem hard

因此，由這個概念可衍伸出 Polynomial Reduction 的意義：

### Polynomial Reduction


> By reducing solving problem A to solving problem B,
we use the easiness of B to prove the easiness of A
>> 用 B 很簡單來證 A 很簡單

:::success
#### 證一個 problem 沒有 polynomial time algo 的方法：
:::

假設我們要證一個 problem B 沒有 polynomial time 的 algo

- 如果我們有一個已知沒有 polynomial time 的 algo 的 decision problem A
- 如果我們也有一個 polynomial time reduction 可以把 A 的problem instance 轉換成 B 的 problem instance

即可證 B 不可能有 polynomial time 的algo

:::success
#### 證一個 problem 是 NPC 的方法：
:::

類似上方證法，但我們不能假設 A 絕對沒有 polynomial time 的algo，而是改為 assume A 是 NPC，由是 NPC 的 A 來polynomial reduce 到 B，即證 B 是 NPC。