NP-hard 定义

一个语言 LL 是 NP-hard 若对任意 NP 中的语言 X 存在关系 X≤pLX\le_p L
定义这个关系为：at least as hard as
并不要求 NP-hard 问题属于 NP

NP-complete

定义语言 LL 是 NP-complete 的如果 1. L∈L\in NP 且 2. L∈L\in NP-hard
从简单上来认识这个 class，可以理解为这是最难解决的 NP 问题

NP-hard 的复杂度性质

如果对于任何一个 NP-hard 的问题，存在一个 多项式复杂度的解 那么任何 NP 问题都可以在 P 时间内解决
因此有两种可能性:

  1. NP-complete 问题全部都属于 P
  2. NP-complete 问题全部需要超过 多项式时间复杂度的求解难度

NP-hard reduction

定义符号 ≤p\le_p 使得 A≤pB⇔A\le_p B \Leftrightarrow ∃f\exists f 多项式函数 s.t. x∈A⇔f(x)∈Bx\in A \Leftrightarrow f(x) \in B
表明 instance B is at least as hard as instance A
注意这里的 f 并不要求单射满射之类，而只需要构造对应就行，甚至对于已知 m∈B,n∉Bm\in B, n\not\in B 我们可以构造 f(x∈A)→m;f(x∉B)→nf(x\in A)\rightarrow m; f(x\not\in B)\rightarrow n 来构建映射关系，但是这要求 A ∈\in P 才能判断 A 是否可解 (但是 B 不需要, 就像是 language 可以既 undecidable 又可以找到某个 l∈Ll\in L 或者 l∉Ll\not\in L, 因为 A 这里要求是对每一个都进行判断而 B 只是对某一个进行判断)
这种方法对于构建比较泛化的问题会有奇效, 但是大多数方法可能是需要建立在原问题类上进行修改的

归纳引理 lemmas

  1. B∈P⇒A∈PB\in P \Rightarrow A\in P
  2. AA NP-hard ⇒\Rightarrow B NP-hard

符号性质

这个符号可以有两种性质

  1. 对于 S∈S\in NP-hard, 则对 ∀x∈L\forall x\in L 都有 x≤pSx\le_p S
  2. 对于 instance (problem) A,BA, B 如果 B 至少比 A 难解决，则可以写作 A≤pBA\le_p B

3-SAT 问题

定义 3-CNF 并联范式

就是将 3 个逻辑语句用 ∨\lor 连接起来形成一个 clause, clause 之间通过 ∧\land 进行连接
这个问题是一个经典的 NP-complete 问题, NP-hard 部分的证明详见 Cook-Levin Theorem

Vertex Cover 问题 VC

定义在一个无向无权图中，点子集 S 对于每一个边至少拥有一个 点 v∈Sv\in S 则称这个子集为一个 vertex cover, 那么对于一个图可否存在一个子集使得实现覆盖且尺寸小于 k 呢?

VC 是 NP-hard 问题

利用 NP-hard reduction 的方法，要么使用对 任意 string 都有 X≤pVCX\le_p VC; 要么证明存在一个 NP-hard 问题 X 使得 X≤pVCX \le_p VC

从最优化问题到决定问题

如果一个问题属于最优化问题，例如找到符合的最大集合等问题，由于 NP 问题需要是 decision 问题(这是定义层的规定：dicidable problem), 需要首先转变为 decision problem: 是否存在大于等于 k 个元素的集合?