P 和 NP 实际上是相同的复杂度类别吗？
P 是否等于 NP 的问题是计算机科学和数学中最深刻且尚未解决的问题之一。这个问题是计算复杂性理论的核心，该理论研究计算问题的固有难度并根据解决问题所需的资源对它们进行分类。
要理解这个问题，必须掌握 P 类和 NP 类的定义。 P 类由决策问题（具有是/否答案的问题）组成，可以通过确定性图灵机在多项式时间内解决。多项式时间意味着解决问题所需的时间可以表示为输入大小的多项式函数。 P 中的问题示例包括对数字列表进行排序（可以使用归并排序等高效算法在 O(n log n) 时间内完成）以及使用欧几里得算法查找两个整数的最大公约数（其运行时间为 O(log （分钟（a，b）））时间）。
另一方面，NP 类由决策问题组成，给定的解决方案可以通过确定性图灵机在多项式时间内验证。这意味着，如果有人为问题提供了候选解决方案，则可以有效地检查其正确性。重要的是，NP并不一定意味着问题本身可以在多项式时间内解决，只是意味着所提出的解决方案可以快速得到验证。 NP 中的问题示例包括布尔可满足性问题 (SAT)，其中人们试图确定是否存在使给定布尔公式为真的变量的真值分配，以及哈密顿循环问题，该问题询问是否存在循环只访问图的每个顶点一次。
P vs NP 问题询问是否每个可以在多项式时间内验证其解决方案的问题（即 NP 中的每个问题）也可以在多项式时间内解决（即在 P 中）。形式上，问题是P是否=NP。如果P等于NP，则意味着每个可以快速验证解决方案的问题也可以快速解决。这将对密码学、优化和人工智能等领域产生深远的影响，因为许多当前棘手的问题可能会得到有效解决。
尽管经过数十年的研究，P 与 NP 的问题仍然悬而未决。尚未有人能够证明 P = NP 或 P ≠ NP。该问题被克莱数学研究所列为七大“千年奖问题”之一，正确答案者将获得 1 万美元的奖金，这凸显了该问题的难度。缺乏解决方案导致了理论和应用计算机科学的重大发展。
与 P vs NP 问题相关的关键概念之一是 NP 完整性。如果一个问题是 NP 的并且与 NP 中的任何问题一样难，则该问题是 NP 完全的，即任何 NP 问题都可以使用多项式时间归约来归约。 NP 完备性的概念是由 Stephen Cook 在其 1971 年的开创性论文中引入的，他在论文中证明了 SAT 问题是 NP 完备性的。这个结果被称为库克定理，具有开创性，因为它提供了 NP 完全问题的具体示例，并建立了识别其他 NP 完全问题的框架。
从那时起，许多其他问题被证明是NP完全的，例如旅行商问题、派系问题和背包问题。 NP完全性的意义在于，如果任何NP完全问题可以在多项式时间内解决，那么NP中的每个问题都可以在多项式时间内解决，这意味着P = NP。相反，如果任何 NP 完全问题无法在多项式时间内求解，则 P ≠ NP。
为了说明 NP 完备性的概念，请考虑旅行商问题 (TSP)。在此问题中，推销员必须访问一组城市，每个城市恰好一次，然后返回起始城市，目标是最小化总行程距离。 TSP 的决策版本询问是否存在总距离小于或等于给定值的城市的旅行。这个问题属于 NP 问题，因为给定一个提议的旅行，人们可以轻松地在多项式时间内验证该旅行是否满足距离约束。此外，TSP 是 NP 完全的，因为 NP 中的任何问题都可以在多项式时间内转化为 TSP 的实例。
另一个例子是派系问题，它询问给定的图是否包含指定大小的完整子图（派系）。这个问题属于 NP 问题，因为给定一个候选团，我们可以在多项式时间内验证它是否确实是所需规模的团。派系问题也是 NP 完全问题，这意味着有效解决它意味着所有 NP 问题都可以有效解决。
P vs NP 和 NP 完备性的研究导致了理论计算机科学中各种技术和工具的发展。其中一种技术是多项式时间约简的概念，它用于表明一个问题至少与另一个问题一样难。从问题 A 到问题 B 的多项式时间归约是一种在多项式时间内将 A 的实例转换为 B 的实例的变换，这样 B 的变换实例的解可用于求解 A 的原始实例。 A可以在多项式时间内简化为问题B，并且B可以在多项式时间内求解，则A也可以在多项式时间内求解。
另一个重要的概念是近似算法的概念，它在多项式时间内为 NP 困难问题（至少与 NP 完全问题一样困难的问题）提供近乎最优的解决方案。虽然这些算法不一定能找到确切的最佳解决方案，但它们通过提供接近最佳解决方案，提供了处理棘手问题的实用方法。例如，旅行商问题有一个众所周知的近似算法，可以保证旅行在度量 TSP 的最佳旅行的 1.5 倍之内（其中距离满足三角不等式）。
解决 P 与 NP 问题的影响超出了理论计算机科学的范围。在密码学中，许多加密方案依赖于某些问题的硬度，例如整数分解和离散对数，这些问题被认为属于 NP 而不是 P。如果 P 等于 NP，这些问题可能会得到有效解决，从而妥协密码系统的安全性。相反，证明 P ≠ NP 将为此类系统的安全性提供更坚实的基础。
在优化中，许多现实问题，例如调度、路由和资源分配，都被建模为 NP 难问题。如果 P 等于 NP，则意味着可以开发有效的算法来最佳地解决这些问题，从而为各个行业带来重大进步。然而，当前 P ≠ NP 的假设导致了启发式和近似算法的发展，为这些问题提供了实用的解决方案。
P 与 NP 问题也具有哲学含义，因为它涉及数学真理的本质和人类知识的局限性。如果 P 等于 NP，则意味着每个带有简短证明的数学陈述都可以被有效地发现，从而可能彻底改变数学发现的过程。另一方面，如果 P ≠ NP，则表明有效计算和验证的内容存在固有限制，凸显了数学结构的复杂性和丰富性。
尽管 P 与 NP 问题缺乏明确的答案，但围绕它的研究使人们对计算复杂性有了更深入的了解，并开发了许多对计算机科学产生深远影响的技术和工具。解决这个问题的探索继续激励和挑战研究人员，推动该领域的进步并扩大我们对计算基本极限的理解。
最近的其他问题和解答 复杂:
- PSPACE 类不等于 EXPSPACE 类吗？
- P 复杂性类别是 PSPACE 类别的子集吗？
- 我们能否通过在确定性 TM 上为任何 NP 完全问题找到有效的多项式解来证明 Np 和 P 类是相同的？
- NP 类可以等于 EXPTIME 类吗？
- PSPACE 中是否存在没有已知 NP 算法的问题？
- SAT 问题可以是 NP 完全问题吗？
- 如果存在可以在多项式时间内解决问题的非确定性图灵机，那么问题是否可以属于 NP 复杂性类别
- NP 是具有多项式时间验证器的语言类别
- P 复杂性类别中的每种上下文无关语言都是如此吗？
- NP 作为一类具有多项式时间验证器的决策问题的定义与 P 类问题也具有多项式时间验证器的事实之间是否存在矛盾？