【算法】P/NP/NPC/NPH 问题
Dandelion 10/10/2022 algorithm
# 概述
多项式时间复杂度：解决问题需要的时间与问题的规模之间是多项式关系。取指数最高项保留作为时间复杂度的表达式。
形如：O(n^k)，其中 n 为问题的规模，k 为某个常数。
# P 问题
- 定义：在多项式时间内可解的问题为 P 问题（Polynomial Problem），即多项式问题。
- 例如：时间复杂度为 O(nlogn) 的快速排序、堆排序算法，O(n^2) 的冒泡排序、直接选择排序算法
# NP 问题
- 定义：非确定性多项式问题（Non-deterministic Polynomial Problem），指问题只能通过验证给定的猜测是否正确来求解。
- 所谓多项式指的是验证猜测可在多项式时间内完成
- 所谓非确定性指的是问题只能通过验证猜测来解，而不能直接求解
- 解决困难但验证简单的问题
- 示例 1：Hamilton 回路，验证一条路是否恰好经过了每个顶点可在多项式时间内完成，但找出一个 Hamilton 回路却要穷举所有可能性，不能直接求解
- 示例 2：大合数的质因数分解，没有给定的公式可直接求出一个合数的两个质因数是什么，但验证两个数是否是质因数却可在多项式时间完成
- 注：之所以要定义 NP 问题，是因为通常只有 NP 问题才可能找到多项式的算法。P 问题是 NP 问题的一个子集。
- 目前，人类尚未解决的问题：是否所有的 NP 问题都是 P 问题？即
P = NP?P = NP意味着任何能够在多项式的复杂度验证的问题也能够在多项式的复杂度解决它- NPC 问题的存在，使得人们相信
P ≠ NP
# NPC 问题
- 多项式规约（Polynomially Reducible）：问题 A 的所有实例都能够在多项式的时间复杂度内转化为问题 B 的所有实例
- 规约后，如果问题依然是一个 NP 问题，就把它称作 NP-complete 问题
- 规约后，如果问题不是一个 NP 问题，就把它称为 NP-hard 问题
- 如：一元一次方程的问题可以规约成一元二次方程的问题
- 定义：NP-完全问题（Non-deterministic Polynomial Complete Problem），满足以下条件：
- 它是一个 NP 问题
- 所有的 NP 问题都可以用多项式时间约化到它
- 示例 1：逻辑电路问题，给定一个逻辑电路，问是否存在一种输入使输出为 true
- 示例 2：Hamilton 回路、旅行商问题
- 注：NPC 问题是 NP问题 的子集
# NPH 问题
- 定义：NP-困难问题（Non-deterministic Polynomial Hard Problem），满足 NPC 问题定义的第二条但不一定要满足第一条
- NPH 问题要比 NPC 问题的范围广，但不一定是 NP 问题
- 由于 NP-Hard 问题放宽了限定条件，它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决
# 总结
很多关于密码学的问题都是基于
P ≠ NP来的，正是基于这种假设才使各种加密算法暂时不能被轻易的破解。
如果证明了P ≠ NP还好说，也就印证了一部分科学家的假设，一旦证明出P = NP，那将可能会导致一些颠覆性的变化。
大多数 NP 问题都是不能在多项式的复杂度内解决的，所以一旦P = NP，就可以将任何一个 NP 问题转化为一个 P 问题。