评估计算复杂性

计算机科学评估计算复杂性，是看它消耗的资源，具体来说就是时间和内存（空间）。

基于时间和空间复杂性，我们有:\(NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE\)
（其中 \(⊆\) 表示子集关系）。

图来自：https://en.wikipedia.org/wiki/Complexity_class

对上图和公式的解释：

NL 非确定性对数空间

NL（Nondeterministic Logarithmic space 非确定性对数空间）：NL类的问题可以被非确定性图灵机在对数量级的空间内解决。这意味着解决这些问题所需的内存空间与输入大小的对数成正比。

参看: 对数的本质是把乘除法降维成加减法

P 多项式时间

P（Polynomial time 多项式时间）：P类问题可以被确定性图灵机在多项式时间内解决，即解决这些问题所需的时间与输入大小的某个多项式成正比。

NP 非确定性多项式时间

NP（Nondeterministic Polynomial time 非确定性多项式时间）：NP类问题的一个解决方案可以被非确定性图灵机在多项式时间内验证。

PSPACE 多项式空间

PSPACE（Polynomial space 多项式空间）：PSPACE类问题可以在多项式量级的空间内解决，无论解决时间长短。

EXPTIME 指数时间

EXPTIME（Exponential time 指数时间）：EXPTIME类问题可以在指数时间内解决，即解决这些问题所需的时间随输入大小的增加而极速增长。

EXPSPACE 指数空间

EXPSPACE（Exponential space 指数空间）：EXPSPACE类问题可以在指数量级的空间内解决，即解决这些问题可能需要非常大量的内存空间。

这些类别之间的包含关系（⊆）表示每个类别都是随后类别的一个子集。例如，所有P类问题都是NP问题，但并非所有NP问题都是P类问题。这些关系帮助我们理解不同计算问题的复杂性程度以及它们之间的联系。

上面复杂度排序中，为啥空间比时间复杂？

通常，空间复杂性被认为是比时间复杂性更“基础”，因为即使有足够的时间，如果没有足够的空间存储必要的信息，问题也无法解决。

图：“精卫填海”的神话场景插画，每次能携带的土石有限，时间无限的话，问题也难以解决。

对数，多项式，指数 三个层次

在计算复杂性理论中，对数、多项式和指数主要描述的是算法的运行时间或空间需求随输入大小的增长速度。这些术语形成了一种层次结构，从效率最高到最低：

对数（Logarithmic）：对数增长表示算法的资源需求随输入大小增长得非常慢。例如，对数时间复杂度通常表现为 \(O(\log_{}{n} )\)，意味着每当输入大小翻倍时，所需资源只增加一个固定量。

多项式（Polynomial）：多项式增长是相对适中的。多项式时间复杂度如 \(O(n)\)、\(O(n^2)\) 或 \(O(n ^3)\) 等，表示资源需求随输入大小呈多项式关系增长。在实际应用中，多项式时间通常被视为可接受的效率。

指数（Exponential）：指数增长意味着资源需求随输入大小极快增长。例如，指数时间复杂度可以是 \(O(2 ^n)\) 或 \(O(n!)\)，这意味着即使输入大小稍微增加，所需的资源也会迅速变得巨大。

图：资源需求随输入大小增长速度

在算法和问题分类中，我们总是希望达到尽可能低的复杂性级别。

P问题 与 NP 问题

尽管NP问题的解决方案可以在多项式时间内被验证，但并不意味着这些解决方案总是可以在多项式时间内被找到。

P类问题的特点是它们的解决方案不仅可以被快速验证，而且可以被快速找到。

将P问题比作拼图的话，可以想象一个简单的拼图，比如一个只有几十块的儿童拼图。这种拼图即使没有提示，大多数人也可以在相对较短的时间内完成。在这个比喻中，完成拼图的过程就像找到P问题的解决方案，而且这个过程并不需要花费很长时间或非常复杂的思考。

图：P问题可比作只有几十块的儿童拼图

NP-完全 与 NP-困难

NP-完全问题的例子：旅行商问题（TSP）：在物流和运输规划中，旅行商问题要求找到最短的路径，经过一系列城市并返回出发点。这个问题在现实世界中的应用包括货物配送、航线规划等。

NP-困难问题的例子：图着色问题：在网络设计、电子电路布局、调度问题中，图着色问题需要确定最少的颜色数目，以使图中任何两个相邻的顶点都不同色。这个问题在分配资源（如频率分配、教室调度）时特别有用。

理解NP-完全和NP-困难问题的区别，可以想象两个不同类型的难题：

NP-完全问题 （NP-Complete）：想象你有一个非常复杂的拼图，比如一千片的拼图。如果有人给你一个拼好的图案，你可以相对容易地验证这个拼图是否正确。这就像NP-完全问题，一旦有了解决方案，验证它是正确的还是相对容易的。但是，实际上找到这个解决方案（即拼好这个复杂的拼图）是非常困难的。

图：有一千片的拼图

NP-困难问题 （NP-Hard）：现在，想象你需要解决一个更难的问题，比如一个复杂的三维立体拼图。这个问题比普通的拼图难多了，而且即使有人给你一个解决方案，验证这个解决方案是否正确也可能非常困难。这就是NP-困难问题，它们至少和NP-完全问题一样难，有时甚至更难，因为验证解决方案的正确性也可能是一个挑战。

图：有上万块的立体拼图

简而言之，NP-完全问题是那些解决方案难以找到但容易验证的问题，而NP-困难问题则是至少和NP-完全问题一样难，甚至可能在验证解决方案上也非常困难的问题。

NP 问题的使用场景

最常被提到的NP问题的特殊性在于其解决方案虽易于验证，却难以发现。在计算机科学和相关领域中非常重要，主要用于以下几个场景：

优化问题：许多NP问题是优化问题，即寻找最优解的问题。例如，在物流和运输中，旅行商问题（TSP）是一个典型的NP问题，它涉及寻找访问一系列城市并返回起点的最短路径。解决这类问题可以帮助公司节约成本和时间。

密码学：在密码学中，某些加密方法（如RSA算法）的安全性基于NP问题的难度。例如，一个大的整数的因数分解是一个NP问题。加密系统的安全性依赖于这类问题当前无法在多项式时间内有效解决。

计划和调度问题：在制造业、资源分配和项目管理中，需要解决各种调度问题，如机器调度、人员排班等，这些通常是NP难问题。

生物信息学和化学：在生物信息学中，比如在DNA序列分析、蛋白质结构预测中，很多问题都可以归类为NP问题。

网络设计：在网络理论中，比如互联网路由、社交网络分析中，找到最有效的网络连接方式往往是NP问题。

游戏理论和经济学：在分析经济模型或游戏策略时，确定最优策略往往涉及NP问题。

这些场景表明，尽管NP问题在理论上很难解决，但它们与实际生活和工业应用紧密相关。解决这些问题可以帮助提高效率、节约成本，甚至保护信息安全。虽然许多NP问题在理论上难以有效解决，但在实践中，人们常常通过近似算法、启发式方法或特定领域的技巧来寻找足够好的解决方案。

总结

计算复杂性理论是计算机科学的核心领域，专注于分析算法所需资源的时间和空间。

核心类别包括NL（非确定性对数空间）、P（多项式时间）、NP（非确定性多项式时间）、PSPACE（多项式空间）、EXPTIME（指数时间）和EXPSPACE（指数空间），这些类别揭示了计算问题的层级结构和相互关系。

最常被提到的NP问题的特殊性在于其解决方案虽易于验证，却难以发现，在计算机科学和相关领域中有广泛应用。