归约

考虑这么两个问题，A 和 B。如果 A 可通过下述步骤求得解：

输入：A 的一个实例，α

  1. 将 α 转换为 B 的一个实例，β
  2. 解决 β，获得一个解
  3. 根据 β 的解，获得 α 的解

那么，A 可被归约为 B。

假设对于问题 A 的一个大小为 n 的实例 α：

  • 问题 B 的实例 β 可以在 p(n) 时间内被构建出来
  • 问题 A 对于 α 的解可经由问题 B 对于 β 的解在 p(n) 的时间内得出

那么这个归约可以说是 p(n) 时间归约。

假如说 p(n) = O(nc) 是一个多项式函数，那么这个归约就是多项式时间归约，写作 A ≤P B。

如果问题 B 具有一个多项式时间算法，那么 A 也有！如果 B 能够被轻松解决，那么 A 也能！

判定问题

判定问题指的是输出为“是”或“否”的问题。

Decision vs Optimization

  • Decision Problem: Given a directed graph G with two given vertices u and v, is there a path from u to v of length ≤ k?
  • Optimization Problem: Given a directed graph G with two given vertices u and v, what is the length of the shortest path from u to v?

最佳化问题都可被转换为判定问题。

判定问题可被归约为最佳化问题。

判定问题之间的归约

给定两个判定问题 A 和 B，如果满足：

  • α 是 YES 实例当且仅当 β 也是 YES 实例
  • 由 α 至 β 的转换的花费时间是关于 α 大小的多项式

那么存在 A 至 B 的多项式时间归约，A ≤P B。

P 问题和 NP 问题

P 代表 “Polynomial（多项式）”。

P 问题囊括了所有可以在多项式时间内解决的判定问题。

NP 代表 “Non-deterministic（非确定性）Polynomial（多项式）”。

NP 问题指的是具有运行时间为多项式时间的验证器（verifier）的，或者说能在多项式时间内验证解的正确性的一类判定问题。

↑ 非严谨的定义 ↑

P/NP 问题：P 和 NP 相等吗？¯\(°_o)/¯

NP 完全问题

如果问题 X 是一个 NP 问题，且对于所有 A ∈ NP，满足 A ≤P X，那么 X 是一个 NP 完全（NP-complete）问题。

证明问题 X 是一个 NP 完全问题：

  1. 证明 X 是 NP 问题
  2. 选择一个已知的 NP 完全问题 A
  3. 证明 A ≤P X

除非 P = NP，否则 NP 完全问题没有多项式时间算法。