3. NP-Complete

定义

A language $L$ is NP-complete if

• $L\in$ NP
• $L$ is NP-hard

证明方法: polynomial-time mapping reduction

定义归纳关系 $A\le_p B$ 表示 $\exists f \text{ s.t. } x \in A\Leftrightarrow f(x) \in B$

引理 lemma

• $B\in P \Rightarrow A \in P$
• $A$ NP-hard $\Rightarrow$ B NP-hard

用法

0. 选取一个已知的 NP-hard 问题 A 来归纳关系 $A\le_p B$
1. 定义问题转变映射: 如何将问题集合 A 的某个确定 instance 转变为 B 的对应的 instance
2. 证明这个转变 f 的时间复杂度是 polynomial
3. 证明 correctness:
   1. 证明一个能解决 A 的 answer 同样在转变的问题中可以以同样的答案解决 B (suppose when given the solution of $x\in A$, then this solution to $f(x)\in B$ is also correct)
   2. 证明能解决 B 的 answer 能以同样答案解决 A

Set Cover 问题

有 n 个工人，每人有各自的技术集合, 目标是在定义的全技术集合中雇佣的工人能覆盖所有的技术 (假设每个技术不会被三个人及以上的拥有)

$VC \le_p SC$

VC 问题是对某个具体 图, 选取节点能否覆盖所有的边
SC 问题是对某个具体 集合, 选取并集能否覆盖所有的集合元素
将 SC 的集合改写为 graph 图, 将各个子集定义为 vertex, 元素定义为 edge 那么 在这个新的 图中如果选取的 set 集合能够 cover 所有的集合就实际上符合了 VC 的答案

Hamiltonian Path (Königsberger Brückenproblem 哥尼斯堡七桥问题)

问题设定：在一个无向图中是否存在一个节点 s 到节点 t 的路径使得经过所有的节点有且仅有一次?
类似问题：Hamiltonian Cycle 形成环且经过每个节点有且只有一次

HM Path $\le_p$ HM Cycle

将 HM Path 的输入图的外面添加一个 special 的点, 那么令 HM Path 的 节点s,t 中间连接这个 special point 形成闭环就是 HM Cycle 问题

Clique 问题