转载请注明出处:小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你,欢迎[点赞、收藏、关注]哦~
目录
4. BPP (Bounded-error Probabilistic Polynomial time)
5. Σk和Πk类 (Polynomial Hierarchy)
8. FPT (Fixed-Parameter Tractable)
10. W类 (Parameterized Complexity)
这是我微调的关于NP问题的GPT,非常好用,推荐给大家: https://chatgpt.com/g/g-6eaZ9eKMd-np-problem-expert
在计算复杂度理论中,指的是一个问题的计算时间𝑚(𝑛)不大于问题大小𝑛的多项式倍数。简单来说,算法的时间复杂度是:O(𝑛^𝑘),n是输入的规模,k通常是常量。
当问题规模趋近无穷时,复杂度的增长率趋近1,表明计算时间基本保持稳定,即计算机的能力与问题的规模是线性增长的比较关系。
常见多项式时间复杂度的关系:
多项式时间与指数时间相对。例如,时间复杂度为O(2^n)或O(n!)的算法则被认为是指数时间的。这些算法的运行时间随着输入规模的增加增长得非常快,通常不可行于大规模问题。
若一个数值算法的时间复杂度可以表示为输入数值n的多项式, 则称其时间复杂度为伪多项式时间。由于n的值是n的位数的幂, 故该算法的时间复杂度实际上应视为输入数值n的位数的幂。
P (Polynomial time):指的是能够在多项式时间内被确定性图灵机解决的问题。这类问题通常被认为是“容易”或“可解”的,因为存在有效的算法。例如,排序算法(如快速排序)和图的最短路径问题都属于P类问题。
NP (Nondeterministic Polynomial time):指的是能够在多项式时间内被非确定性图灵机验证的问题。这类问题的解决方案可以在多项式时间内被验证,但找到解决方案可能需要很长时间。例如,旅行商问题(TSP)和3-SAT问题都是NP问题。
NP-Hard:这些问题至少和NP类问题一样难,但不一定属于NP类。这意味着NP-Hard问题不一定是决策问题,它们可以是优化问题。即使能够验证一个NP-Hard问题的解,其验证过程也不一定在多项式时间内完成。如果对于 NP 中的每个问题 L,存在从 L 到 A 的多项式时间约简,则问题 A 处于 NP-Hard 状态。例如,旅行商问题的优化版本是NP-Hard的。
NP-Complete:这是NP类中最难的问题。如果一个NP-Complete问题能够在多项式时间内被解决,那么所有NP问题都能够在多项式时间内被解决。如果一个问题既是NP又是NP-Hard的,则它是NP-Complete的。NP-Complete问题很特殊,因为NP类中的任何问题都可以在多项式时间内转换或简化为NP-Complete问题。如果可以在多项式时间内求解NP-Complete问题,那么也可以在多项式时间内求解任何 NP 问题。例如,3-SAT问题和哈密顿路径问题都是NP-Complete问题。
要证明一个问题是NP-Complete,通常需要两个步骤:
NP-Hardness:这是对问题难度的一种描述,表示问题的计算复杂性至少和NP问题一样高。换句话说,如果一个问题是NP-Hard的,那么它至少和最难的NP问题一样难。
类别 | 定义 | 特点 | 示例问题 |
---|---|---|---|
P | 可以在多项式时间内求解的问题 | 求解和验证都很容易 | - 排序算法,如快速排序 - 最短路径问题,如Dijkstra |
NP | 给定一个解,可以在多项式时间内验证其正确性的问题 | 求解可能难,但验证容易 | - 3-SAT问题 - 旅行商问题的决策版本 |
NP-Hard | 所有NP问题都可以多项式时间归约到该问题。可能是决策问题或优化问题,也不一定属于NP类 | 验证和求解都可能难,且不一定是决策问题 | - 旅行商问题的优化版本 - 0/1背包问题的优化版本 |
NP-Complete | 属于NP类的NP-hard问题。必须是决策问题 | 验证和求解都很难,且必须是决策问题 | - 3-SAT问题 - 哈密尔顿路径的决策版本 |
co-NP 类问题是与 NP 类问题互补的一类问题。一个问题属于 co-NP 类,如果它的否定问题属于 NP 类。换句话说,如果一个问题的解可以在多项式时间内验证,那么 co-NP 类问题的反例(解不存在的证明)也可以在多项式时间内验证。例如,3-SAT 的否定问题是“判断一个布尔公式是否对所有赋值都不为真”,属于 co-NP 类。
PSPACE 类问题是指那些可以在多项式空间内解决的问题。换句话说,这类问题的算法在解决过程中所需的内存空间是输入大小的多项式函数。例如,很多博弈问题(如国际象棋的决策问题)属于 PSPACE 类。
EXPTIME 类问题是指那些需要指数时间解决的问题。也就是说,解决这类问题的算法在最坏情况下的运行时间是输入大小的指数函数。例如,很多解码和加密问题(如 RSA 解密)属于 EXPTIME 类。
BPP 类问题是指那些可以在多项式时间内由概率算法解决的问题,并且算法的错误概率在一定范围内。例如,许多随机化算法(如蒙特卡罗算法)属于 BPP 类。
Σk和Πk类是多项式层级中的问题类,表示不同层次的复杂性:
L 和 NL 类问题分别是那些可以在对数空间内由确定性和非确定性图灵机解决的问题。L(Logarithmic Space)表示确定性对数空间,NL(Nondeterministic Logarithmic Space)表示非确定性对数空间。例如,连通性问题可以在 NL 类中解决。
APX 类问题是指那些存在近似算法的问题,这些算法可以在多项式时间内找到近似解,并且该解的性能保证在一个常数因子范围内。例如,旅行商问题的近似解属于 APX 类。
FPT 类问题是指那些可以通过某个参数在多项式时间内解决的问题,即使问题本身是 NP-Hard。例如,许多图论问题在图的某些参数(如树宽、路径宽度)固定时可以在 FPT 类中解决。
#P 类问题是指那些计算计数问题,即给定一个 NP 问题,计算有多少个解。例如,计算满足一个布尔公式的赋值数目属于 #P 类。
W类表示参数化复杂度中的一类问题,类似于固定参数可处理性问题。W[1] 和 W[2] 是其中的典型类,表示在特定参数下的复杂性分类。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。