计算机容易做什么，几乎不可能？ 这些问题是计算复杂性问题的核心。 我们为您提供此景观的地图。
不同的复杂性类以分层形式对任务进行排序。 一类可以包含另一类的所有任务，以及需要其他计算资源的任务。这项任务的基本困难是什么？ 这是试图根据所谓的任务进行排序的计算机科学家的基本任务的表述。
难度课 。 这些是包含所有不超过固定数量的计算资源（例如时间或内存）的计算任务的组。 让我们以一个简单的示例为例，该示例有一个很大的数字，例如123 456 789001。有人可能会问：它是素数吗？一个仅除以1且本身除的素数？ 计算机科学家可以用快速算法来回答它-这样它们就不会以任意大的速度开始变慢。 在我们的案例中，事实证明该数字不是素数。 然后我们可以问一个问题：其主要因素是什么？ 但是没有快速的算法可以解决这个问题-仅在使用量子计算机的情况下。 因此，计算机科学家认为这两项任务属于不同的复杂性类别。
尽管在大多数情况下研究人员无法证明一类明显不同于另一类，但难度有许多不同的类别。 班级之间存在差异的证据是该领域最困难和重要的任务之一。
类之间的区别几乎无法区分或显而易见，并且很难很好地理解所有类。 因此，我们将本指南汇编为七个最基本的难度类别。 是的，您将不再混淆BPP和BQP。
P
表示 ：多项式时间
简短说明 ：经典（非量子）计算机可以轻松解决的所有任务。
确切描述 ：P类算法应该在不超过n
c的时间内停止工作并给出正确的答案，其中n是输入数据的长度，c是常数。
典型任务 ：
研究人员想知道的是 ：P与NP一致吗？ 巧合将彻底改变计算机科学，并使大多数密码系统变得毫无意义（但几乎没人相信这一点）。
NP
表示 ：不确定的多项式时间
简短说明 ：经典计算机可以轻松检查是否有解决方案的所有任务。
确切描述 ：如果答案是肯定的，则有一个简短的证明答案正确的证明，那么问题属于NP类。 如果输入是字符串X，并且您需要确定答案是否匹配“是”，则简短证明将是另一个字符串Y，该字符串可用于验证多项式时间中正确的答案“是”。 （Y有时被称为“短见证人”-NP的所有任务都有短见证人，因此可以对其进行检查）。
典型任务 ：
- 单击的任务 。 想象一个带有边和顶点的图-例如，顶点表示社交网络的用户，边表示他们是“朋友”。 一个集团是此图的子集，其中所有人彼此都是朋友。 您可以对图表提出以下问题：点击20个人吗？ 50个人？ 100？ 查找团是NP完成的任务 ，也就是说，其复杂性是所有NP任务中最高的。 但是，拥有一个潜在的答案-50个节点的子集，可能是单击也可能不是单击-很容易验证。
- 业务员的任务 。 给定一组城市之间任何两对之间的距离-是否有办法绕过所有城市，行驶距离小于一定距离？ 例如，推销员能否在不到11,000英里的距离内旅行于美国所有首都？
研究人员想知道什么：P = NP？ 计算机科学专家并没有接近解决这个问题。
PH值
表示 ：多项式层次
简短说明 ：PH是NP的概括。 它包含可以从NP中的任务开始并强加其他难度级别可以获得的所有任务。
确切的描述 ：PH包含带有许多使这些任务复杂化的不同“量词”的任务。 不同量词的一个问题示例：如果给定X，是否存在Y，使得对于每个Z，都存在满足R的W？ 问题中的量词越多，问题就越复杂，多项式层次也就越高。
一个典型的任务是确定是否确实有一个大小为50的点击，而没有大小为51的点击。
研究人员想知道的是 ：还没有人能够证明PH与P不同。这个问题等同于P和NP的相等性，因为如果突然发现P = NP，那么所有PH都将被还原为P（P = PH）。
空格
表示 ：多项式空间约束
简短说明 ：PSPACE包含使用合理数量的内存即可解决的所有任务。
确切的描述 ：在解决PSPACE任务时，您不再担心时间，而只担心算法工作所需的内存量。 计算机科学家已经证明PSPACE包含一个PH，该PH包含一个包含P的NP。
典型任务 ：P，NP和PH中的所有任务都包含在PSPACE中。
研究人员想知道什么 ：PSPACE与P有区别吗？
q
表示 ：具有误差概率限制的量子多项式时间
简短说明 ：所有可以在量子计算机上轻松解决的任务。
确切描述 ：多项式时间内可以在量子计算机上解决的所有任务。
典型问题 ：找到整数的质因子。
研究人员想知道的是 ：到目前为止，已经证明BQP包含在PSPACE中，并且BQP包含P。研究人员不知道BQP是否包含在NP中，但是他们认为这两个类别是无法比较的-NP中包含某些任务，但在BQP中却没有，反之亦然。
超时时间
表示 ：指数时间
简短说明 ：可以在经典计算机上以指数方式解决的所有任务。
确切的描述 ：EXP包含所有先前的类-P，NP，PH，PSPACE和BQP。 研究人员证明了它与P不同-他们发现了属于EXP而不属于P的任务。
典型任务 ：象棋和跳棋等游戏的泛化。 如果棋盘可以是任何大小，那么确定一名球员是否具有优势的任务就成为EXP的任务。
研究人员想知道的是 ：他们想证明PSPACE不包含EXP。 他们认为有些任务是EXP的一部分，而不是PSPACE的一部分，因为有时从EXP解决任务需要花费很多时间。 研究人员知道如何将EXP和P分开。
BPP
表示 ：具有错误概率限制的多项式时间
简短说明 ：可以使用使用随机性的算法快速解决的任务。
确切描述 ：BPP与P相同，不同之处在于该算法可能包括随机做出决策的步骤。 BPP中的算法需要以接近1的概率给出正确答案。
典型的任务 ：您有两个不同的公式给出具有多个变量的多项式。 这些公式是否计算相同的多项式？ 这是检查多项式身份的任务。
研究人员想知道的是 ：BPP和P是否相等，如果相等，那么任何具有随机性的算法都可以从随机性中消除。 他们认为-对于每个有效的随机算法问题，都有一个有效的确定性算法-但他们尚未能够证明这一点。