NP 理论初探

P 与 NP

P: 存在多项式算法，可以解出一个 solution
NP: 存在多项式算法，给定 solution 可以判定输入是否合法
- NP-Complete: 所有 NP 问题都可以归约到 $A$ ，且 $A$ 是 NP 问题，则 $A$ 是 NP-Complete 问题
- NP-Hard

$B \le_p A$ 或者 $B\to A$ ，表示存在一个多项式算法 $f$ ：

NP 问题判定定理 $1$

若 $B\to A$ ，且 $A$ 是 P 问题，则 $B$ 也是 P 问题。

【证明】
因为 $A$ 问题内多项式时间 $O(f(x))$ 内可解，而又存在多项式算法 $O(g(x))$ 可以转化输入，则可以在 $O(f(x)+g(x))$ 的时间内解决 $B$ . $\square$

优化问题 (Optimization Problem)

NP Problem 是在寻找可行解，而其对应的优化问题则是在找最优解。

如果某个优化问题对应的判定问题是 NP Complete 的，则这个优化问题为 NP Hard 的。

考虑判定问题 $X$ 和对应的优化问题 $Y$ ，如果

则我们可以在多项式时间内解决 $X$ ，从而 $P=NP$ ，那么 $Y$ 就是 NP-Hard 的。