NP问题

NP 问题的定义

• NP 问题：可以在多项式时间内验证 YES or NO（基于非确定性图灵机）
• NP-Hard 问题：
  • 一个问题 \(P\) 是 NP 难问题，如果 \(\forall Q\in NP,Q\leq_{P}P\)
• NPC 问题：
  • 该问题是 NP 问题
  • 已知的某个 NPC 问题可以在多项式时间内归约到该问题。
    • 这保证其是 NP 问题中最难的

归约

定义 （问题 \(P\) 到 \(Q\) 的归约）

判定问题 \(P\) 到 \(Q\) 的归约（\(P\leq Q\)）为一个转换函数 \(T(x)\)，满足： - 它能够将问题 \(P\) 的任意一个合法的输入 \(x\) 转化为 \(Q\) 的一个合法的输入 \(T(x)\)。 - \(P\) 问题对于任意输入 \(x\) 的输出是 YES，当且仅当 \(Q\) 问题对输入 \(T(x)\) 的输出是 YES

• 多项式归约
  • 表达为 \(\leq_{P}\)，P 即多项式（polynomial）

---

背包问题和伪多项式时间

算法问题计算时间复杂度，一般是一个 \(O(f(n,m,\dots))\) ，其中 \(f\) 是一个函数，\(n,m,\dots\) 是一个参数

但需要注意，参数实际上分为： - 结构性参数，是题严格直接给出的。 - 如冒泡排序的 \(n\)，表达数组元素的个数，我们只关心这个数值，不关心其规模，所以用 \(n\) 表示。\(n\) 是数字个数的多少 - \(n\) 只用来决定外循环的次数，是数字个数的多少 - 数值性参数，我们对齐操作只关心他的数值大小。 - 如质数判断问题中的 \(n\)，我们对齐要进行数值操作，关心其输入规模。 - \(n\) 是一个我们关心的数值

总体而言，根据参数的不同，我们会出现伪多项式时间和多项式时间 多项式时间算法 (polynomial time algorithm) 表示：算法的复杂度与输入的规模呈多项式关系。 伪多项式时间算法 (pseudopolynomial time algorithm) 是表示：算法的复杂度与输入规模呈指数关系，与输入的数值大小呈多项式关系。

例如背包问题 \(O(nW)\)，where \(n\) 是物品序列大小，\(W\) 是背包容量 - \(n\) 是一个结构性参数，因为其只表示物品的个数 - \(W\) 是一个数值型参数，我们要对其进行数值操作。 - 所以单纯把 \(W\) 也看作结构性参数而不考虑实在规模的 \(O(nW)\) 被称为伪多项式时间复杂度，原因在于： - 如果 \(W\) 以输入规模的形式提供，则量度时间复杂度，应该考虑输入的位数，即 \(\log W\)

- 在背包问题的复杂度应该写成 $O(n2^{ \log W})$)，是指数复杂度
- 这也是为什么背包问题不能说其有 $P$ 算法。