多项式时间验证

简介

多项式时间验证是理论计算机科学和计算复杂性理论的一个领域。它指的是一个算法在多项式时间内验证一个提出的解或陈述的效率。计算复杂性理论根据问题的难度和解决它们所需的资源对其进行分类。多项式时间是效率的衡量标准，能够在多项式时间内解决的问题在算法复杂性方面被认为是可处理的或“简单的”。控制多项式时间的概念通常与一类称为 NP（非确定性多项式时间）的问题相关。如果一个问题在 NP 中，那么给定一个提出的解，就可以用一个确定性多项式时间算法来检查它。换句话说，如果有人声称找到了 NP 问题的解，那么就应该能够快速验证该解是否正确。该概念在决策问题领域至关重要，在这些问题中，答案是“是”或“否”。多项式时间检查意味着一旦给出了候选解，其正确性就可以被有效地检查。这与 NP 问题形成对比，在 NP 问题中，找到解可能在计算上很困难，但验证解相对容易。多项式时间验证的概念对计算的几个领域都有影响，包括密码学、优化和算法设计。它在理解计算效率的限制方面起着核心作用，并构成了计算复杂性研究中 P（可在多项式时间内解决的问题）和 NP 等类别的基础。总之，多项式时间验证是一个关键概念，它侧重于验证问题解的有效性。这是计算复杂性理论的核心思想，有助于根据问题的固有难度以及算法解决或控制它们的有效性来对其进行分类。

多项式时间验证的历史

多项式时间验证的概念深深植根于计算复杂性理论的发展，这是一个探索计算问题的内在难度以及解决它们所需的资源的领域。多项式时间验证的历史进程与复杂性理论的更广泛演变紧密相连。以下是简史：

• 早期复杂性类别（20 世纪 60-70 年代）：计算复杂性方面的基础工作始于 Stephen Cook 在其 1971 年的里程碑式论文《定理证明过程的复杂性》中引入 P（多项式时间）和 NP（非确定性多项式时间）等类别。Cook 的工作为理解算法效率和问题的内在难度奠定了基础。
• Cook 定理（1971 年）：Stephen Cook 的开创性成果，即 Cook 定理或 Cook-Levin 定理，确立了 NP-完备性的概念。这引入了问题之间多项式时间归约的概念，表明 NP 中某些问题与 NP 中最难的问题一样难。
• 多项式时间控制（20 世纪 70-80 年代）：多项式时间控制的思想作为 NP-完备性框架的自然结果而出现。事实证明，确保任务的高效解决（在多项式时间内）是一个独立且重要的概念。该概念得到了形式化，研究人员开始研究其解可以被快速验证的问题类别。这导致 NP 被定义为具有可在多项式时间内验证的解的问题类别。
• Cook 的贡献（20 世纪 70 年代至今）：Stephen Cook 对复杂性理论做出了重要贡献。他的工作为理解复杂性类别的结构及其之间的关系奠定了基础。Cook 定理为 NP-完备性研究打开了大门，研究人员研究了 NP 中的各种问题，并通过多项式时间归约表明了它们的等价性。
• Karp（1972 年）的 21 个 NP-完全问题：Richard Karp 基于 Cook 的工作，确定了 21 个特殊的 NP-完全问题。这些问题多种多样，涵盖了广泛的应用，表明 NP-完备性无处不在。
• 复杂性类别的演变（20 世纪 80 年代至今）：随着 PSPACE、EXPTIME 等更细致类别的引入，复杂性类别的研究得到了扩展。研究人员继续研究这些类别之间的关系，并研究了可以有效处理或控制的问题的特征。
• 实际意义和应用：多项式时间检查的概念具有实际意义，特别是在密码学、算法设计和优化领域。这有助于开发对许多问题都有效的实用算法。多项式时间验证的历史发展与计算复杂性的更广泛研究交织在一起，并在塑造我们对算法性能和问题复杂性的理解方面发挥了至关重要的作用。研究人员继续在此基础上进行探索，为该领域的持续发展做出贡献。

多项式时间验证的优势

多项式时间控制是计算复杂性理论中与算法和问题复杂性相关的概念。如果一个问题具有多项式时间验证算法，这意味着如果问题得到解决，其正确性可以在多项式时间内得到验证。它在计算机科学和算法分析领域具有多项优势：

1. 有效验证：多项式时间检查意味着检查解的正确性是有效的。在实际应用中，这意味着在解可以轻松在多项式时间内验证的问题中，可以快速验证所提出解的正确性。
2. NP 类：多项式时间检查与 NP（非确定性多项式时间）复杂性类别密切相关。NP 问题是指可以通过确定性算法快速（在多项式时间内）验证所提出解的问题。许多重要且实际的问题都属于 NP 类别。
3. P vs NP：多项式时间控制的概念是 P vs. NP 问题（计算机科学中最著名的未解决问题之一）的核心。P 代表可以在多项式时间内解决的问题，而 NP 是指其解可以在多项式时间内验证的问题。P 是否等于 NP 的问题仍未解决，但如果 P 等于 NP，则意味着高效可控制的问题也存在高效的求解算法。
4. 实用算法：通常可以为多项式时间验证任务构建算法，这些算法也可以在多项式时间内解决。在实际应用中，这很有用，因为它意味着当找到解时，验证它也很有效。
5. 密码学：一些密码学协议和系统依赖于找到解决验证简单的问题的方案。多项式时间验证是密码学算法设计和安全分析的关键因素。
6. 减少决策问题：许多问题可以转化为决策任务，任务是决定给定的解是否正确。多项式时间控制简化了将问题归约为决策问题的过程，这有助于分析和分类问题的复杂性。

总之，多项式时间验证的优势在于其效率，这不仅对理论计算机科学而且对实际算法设计都有影响，尤其是在与 NP 类问题相关的情况下。

多项式时间验证的缺点

虽然多项式时间具有多项优势，但了解与之相关的局限性和潜在缺点也很重要。

1. 范围有限：多项式时间检查是一个适用于非确定性多项式时间（NP）问题的特殊标准。并非所有问题都属于此类别，某些问题可能具有更复杂的验证过程，使其难以在多项式时间内进行分类。
2. 不保证多项式时间解：尽管多项式时间控制确保了对所提出解的有效控制，但这并不一定意味着找到解本身很容易。有些问题的验证是多项式的，但找到解在计算上很困难。
3. P vs. NP 未解问题：由多项式时间验证算法（NP）解决的问题与多项式（P）问题之间的关系是计算机科学中的一个重大未解问题（P vs. NP 问题）。目前尚不清楚 P 是否等于 NP，解决这个问题对算法效率和计算的性质具有重大影响。
4. 实际使用：NP 中的某些问题可能具有多项式时间控制，但缺乏可以有效找到解的实际算法。多项式时间验证不一定意味着在寻找解方面具有实际效率，尤其是在处理大型问题实例时。
5. 密码学挑战：尽管对于某些密码学协议而言，多项式时间验证是可取的，但寻找同时包含计算上困难的解和验证的这类问题对于密码学系统的安全性至关重要。在验证的简易性和可解性之间取得适当的平衡对于密码学应用至关重要。
6. NP 复杂度的差异：NP 是一个广泛的类别，其中包含寻找和验证解的难度程度各不相同。多项式时间检查并未考虑到 NP 中问题内在难度的细微差别。
7. 恒定因子决定：多项式时间是一个理论上的数量，不包括实际算法相关的恒定因子。然而，具有多项式时间复杂度的算法可能不实用，如果多项式的次数非常高或恒定因子很大。

总之，虽然多项式时间控制提供了有价值的见解和益处，但在寻找解时，考虑问题的更广泛背景和复杂性非常重要，尤其是在存在 P vs. NP 等未解问题时。

多项式时间验证的性质

多项式时间检查是一个与检查问题解的正确性效率相关的概念。它经常与多项式时间复杂度进行比较，多项式时间复杂度指的是解决问题的效率。多项式时间控制的概念在决策问题和 NP（非确定性多项式时间）问题类别中尤其重要。以下是多项式时间放大的一些性质：

1. 确认算法：多项式时间验证意味着存在一个验证算法，该算法可以在多项式时间内验证所提出解的正确性。证明者同时接收问题的输入实例和所提出的解作为输入，并确定解是否正确。
2. 证明或见证：提出的解通常附带一个“证明”或“见证”，以证明其正确性。验证算法使用此证明来有效地验证解。
3. 性能：验证过程高效，并且可以在多项式时间内完成。换句话说，验证算法的时间复杂度是输入大小的多项式。
4. 多项式时间关系：输入实例的大小与控制器花费的时间之间的关系是多项式的。这意味着随着输入大小的增加，验证过程不会变得不合理地缓慢。
5. 非确定性多项式类（NP）：多项式检查与 NP 类密切相关。仅当存在多项式时间检查器时，决策问题才属于 NP。NP 问题是指其所提出解可以被快速验证的问题，尽管找到解可能并不快。
6. 完美性：NP-完备性是决策问题的性质，这些问题既属于 NP，又在某种意义上与 NP 中最难的问题一样难。多项式时间检查的概念是 NP-完备性理论的基础。
7. 示例：布尔可满足性（SAT）和旅行推销员问题等问题属于 NP，因为可以在多项式时间内验证提出的解。然而，根据我截至 2021 年 9 月的最新更新，尚无已知的多项式时间算法来解决这些问题。理解和表征 NP 类以及多项式时间检查是理论计算机科学的核心方面，尤其是在对算法复杂性和计算问题进行分类的背景下。

算法

多项式时间验证器算法是一个通用的模型，用于在多项式时间内验证问题的解。它通过一个验证算法来封装多项式时间验证的本质，该算法有效地检查所提出解相对于原始问题实例的有效性。算法打印“接受”表示解被认为有效，或打印“拒绝”表示解被发现无效。证明者的多项式时间复杂度确保了验证过程的效率，特别是对于 NP 问题。

多项式时间控制中的问题

多项式时间检查是指属于 NP（非确定性多项式时间）复杂度类的那些问题。这些问题具有这样的特性：基于所提出的解，可以在多项式时间内有效地检查解的正确性。以下是一些属于多项式时间放大类别的问题示例：

1. 布尔可满足性（SAT）：一个布尔公式，是指将变量赋值布尔值使得公式为真。所提出的真值规定可以在多项式时间内验证。
2. 图着色：给定一个图和顶点颜色，是否可以给图着色，使得没有两个相邻的顶点具有相同的颜色？提出的颜色可以在多项式时间内进行控制。
3. 哈密顿路径：图是否具有哈密顿路径（访问每个顶点恰好一次的路径）？所提出的哈密顿路径的验证可以通过检查它访问每个顶点恰好一次以及覆盖了所有边来完成。旅行推销员问题（TSP）：给定一组城市以及它们之间的距离，是否存在一个访问每个城市恰好一次并返回起点的最小距离的行程？可以通过检查它访问每个城市恰好一次并且总距离是正确的来确认一个计划好的行程。
4. 子集和：给定一组整数和一个目标和，是否存在一个整数子集可以得到目标和？通过检查其元素之和是否等于目标和来检查所提出的子集。
5. 面积满足：布尔循环的输入是否有使输出为真的值？输入值的所提议赋值可以在多项式时间内验证。背包问题：给定一组物品，每个物品都有重量和价值，以及一个容量有限的背包，是否可以选择一个物品子集，使得它们的总重量小于或等于容量，并且总价值最大化？要检查所提出的物品子集，必须检查重量限制并计算总价值。
6. 3SAT（3-可满足性）：这是布尔可满足性的一种特殊情况，其中每个语句包含恰好三个文字。这仍然是 NP-完全问题，并且 3SAT 实例的解（真值赋值）可以在多项式时间内验证。这些示例显示了问题，尽管可能没有已知的多项式时间算法来找到解，但可以在多项式时间内高效地检查所提出解的有效性。这种特性使这些问题属于 NP 类别。

多项式时间验证的解决方案

多项式时间检查，通常与计算机理论中的多项式时间复杂度概念相关，指的是在多项式时间内检查问题解的正确性的能力。这在复杂性类别中至关重要，特别是对于解本身是多项式或指数函数的逆问题。这个概念经常与 NP（非确定性多项式时间）复杂性类别一起讨论。在 NP 中，可以在多项式时间内快速验证解（即使找到解是一项更艰巨的任务（不一定在多项式时间内））。NP 问题被认为是“易于检查的”。以下是多项式时间放大工作原理的快速概述：

• NP 中的问题：如果可以在多项式时间内检查一个问题，则该问题属于 NP。这意味着如果有人声称找到了问题的解，则可以快速检查它是否正确。
• 验证算法：存在一个多项式时间验证算法，该算法可以验证解的正确性。此验证器同时接收输入和所需的解，并确定解是否正确。
• 多项式时间：验证过程应在多项式时间内完成，具体取决于输入的大小。这一点很重要，因为目标是确保检查过程的有效性。
• 证明：声称的解通常附带一个“证明”或“见证”，这是帮助验证者确认解正确性的附加信息。证明通常比问题的原始实例小得多。示例：考虑寻找图上的哈密顿循环。虽然找到哈密顿循环可能是一项艰巨的任务，但如果有人声称找到了哈密顿循环，你可以通过验证它确实恰好访问每个顶点一次并形成一个循环来轻松验证它。总之，多项式时间检查是复杂性理论中的一个关键概念，尤其是在研究 NP 问题时。它突出了易于证明但难于解决的问题与难于解决且难于控制的问题之间的区别。

用于多项式时间验证的 C 程序

说明

• 主文件
  • #include：提供输入和输出功能的函数。
  • #include：提供布尔数据类型（bool）以及 true 和 false 值。
• 宏
  • #define MAX_VERTICES 100：定义图的最大顶点数的宏。
• 函数
  • isHamiltoniancycle：此函数检查给定路径是否为图中的哈密顿循环。它将邻接矩阵（graph）、路径和顶点数（n）作为参数。该函数检查路径是否为有效循环，是否恰好访问每个顶点一次，以及连续顶点之间是否存在边。如果路径是哈密顿循环，则返回 true，否则返回 false。
  • 主函数
    • 初始化一个表示为邻接矩阵的示例图。
    • 指定一个哈密顿循环（路径）实例。
    • 调用 isHamiltonianCycle 函数来检查给定路径是否为哈密顿循环。
    • 打印结果。

示例输出

The given path is a Hamiltonian Cycle.

用于多项式时间验证的 Java 程序

说明

• 哈密顿循环方法
• 此方法检查给定路径是否为图中的哈密顿循环。
• 它将邻接矩阵（graph）和路径作为参数。
• 该方法检查路径是否为有效循环，是否恰好访问每个顶点一次，以及连续顶点之间是否存在边。
• 如果路径是哈密顿循环，则返回 true，否则返回 false。
• 主方法
  • 初始化一个表示为邻接矩阵的示例图。
  • 指定一个哈密顿循环（路径）实例。
  • 调用 isHamiltonianCycle 方法来检查给定路径是否为哈密顿循环。
  • 打印结果。

示例输出

The given path is a Hamiltonian Cycle.

多项式时间验证的复杂度

多项式时间检查的复杂度与可以在多项式时间内由确定性图灵机检查的问题相关。这类问题属于 NP（非确定性多项式时间）复杂度类别。在计算机科学和计算复杂性理论中，问题根据其解决难度进行分类。P 类（多项式时间）由确定性图灵机可以在多项式时间内解决的决策问题组成。另一方面，NP 包含这样的决策问题：给定一个解，可以用多项式时间由确定性图灵机快速验证。以下是涉及的概念的细分：多项式时间验证：如果一个决策问题可以在给定解的基础上在多项式时间内进行检查，则该问题属于 NP。非确定性多项式时间（NP）：NP 是指这样的决策问题类别：其提出的解可以用确定性图灵机在多项式时间内快速验证。请注意，“非确定性”一词并不意味着机器本身是非确定性的；也就是说，在 NP 的上下文中，非确定性图灵机可以在多项式时间内猜测出解。P vs NP：P 是否等于 NP 是计算机科学中最重要的问题之一。如果 P 等于 NP，那么任何其解可以快速验证的问题也可以快速解决。如果 P 不等于 NP，则存在一些问题，其证明比解决它们容易得多。复杂度类别：P 和 NP 只是复杂度类别层级中的两个类别。存在一些问题，它们可能比 NP 更难，通常被归入 NP-hard 和 NP-complete 等更高的复杂度类别。总之，我们可以说多项式时间控制是 NP 问题的一个属性。这些是您可以有效地检查解是否正确的那些问题。P 是否等于 NP 的问题仍未解决，并且是我们理解计算复杂性的核心。

多项式时间验证的结论

总之，多项式时间控制的概念是计算复杂性理论的一个基本方面。以下是一些总结要点：

• NP 类：多项式时间检查与 NP（非确定性多项式时间）复杂度类别密切相关。NP 问题的特征在于，一旦获得解，它就可以由确定性图灵机在多项式时间内进行检查。
• 高效验证：多项式验证的重要性在于验证解的效率。即使找到解在计算上很困难，一旦提出了一个解，它也可以相对快速地进行验证。
• P vs NP 问题：P（可在多项式时间内解决的问题）是否等于 NP 是计算机科学中一个重要的未解问题。如果 P 等于 NP，则意味着具有有效可验证解的问题也具有有效可找到的解。如果 P 不等于 NP，则表明存在一些问题比控制它们更难解决。
• 复杂度层级：多项式时间检查是复杂度类别更大层级的一部分，包括 P、NP、NP-complete 和 NP-hard。这些类别有助于根据问题的内在计算难度对其进行分类。
• 实际意义：尽管 P vs. NP 的理论意义深远，但许多多项式时间验证问题在实践中被认为是可处理的。高效验证 NP 问题解的算法在密码学、优化和人工智能等领域具有价值。
• 并行性和检查：多项式时间检查的效率会影响并行计算。许多验证过程可以并行化，这可能导致实际解决方案，即使整体问题解决方案在计算上仍然复杂。
• 近似算法：在找不到精确解在计算上不可行的情况下，多项式时间检查也支持近似算法的开发。这些算法提供的解可能不是最优的，但足够接近，可以有效地进行控制。
• 交互式证明系统：多项式时间验证与交互式证明系统的概念有关。这些系统涉及证明者和验证者之间的通信，并用于证明解的正确性。高效的交互式证明系统在安全通信和密码学协议中有应用。
• 密码学重要性：多项式时间验证的概念在密码学领域至关重要。密码学协议通常依赖于存在易于验证但难于解决的问题，这确保了各种密码系统的安全性。
• 搜索启发式：在目标是在多个可能性中找到最佳解的优化任务中，多项式时间检查允许开发搜索启发式。这些启发式可以通过快速拒绝不符合有效标准的解来有效地指导搜索过程。对量子计算的影响：多项式时间检查对量子计算有影响。理解哪些问题具有高效的控制过程可以为量子计算机在解决某些类型的问题方面提供的潜在优势提供见解。