多项式时间验证

本文概述

• 哈密​​顿循环问题：
• P和NP类的关系
• 简化
• 多项式时间减少

在讨论NP完全问题的类别之前, 必须先介绍验证算法的概念。

许多问题很难解决, 但是它们具有以下特性：如果提供了解决方案, 则很容易对解决方案进行身份验证。

哈密​​顿循环问题：

考虑哈密顿循环问题。给定一个无向图G, G是否有一个循环访问每个顶点一次？此争议没有已知的多项式时间算法。

注意：-这意味着即使没有为具有特定顶点的哈密顿循环提供特定的路径, 也无法在具有多项式时间的图形中构建哈密顿循环, 但是你无法在多项式内验证哈密顿循环时间

无花果：哈密顿周期

让我们了解一下, 图确实具有哈密顿循环。有人会很容易说服这一点。他们会类似地说：“时间段是hv3, v7, v1 …… v13i。

然后, 我们可以检查图并检查这确实是一个合法周期, 并且它恰好访问了图的所有顶点一次。因此, 即使我们不知道解决哈密顿循环问题的有效方法, 也存在一种有益的方法来验证给定的循环确实是哈密顿循环。

注意：-为了在无向哈密顿循环图G的多项式时间内进行验证。必须给出哈密顿循环的精确/特定/确定路径, 然后才能在多项式时间内进行验证。

证书的定义：-包含在顶点给定路径中的一条信息称为证书

P和NP类的关系

1. NP中含有P
2. P = NP

1. 观察到NP中包含P。换句话说, 如果我们可以在多项式时间内解决问题, 那么我们确实可以在多项式时间内验证该解。更正式地说, 我们不需要查看证书（无需指定特定路径的顶点/中间层）即可解决该问题；我们还是可以用多项式时间来解释它。
2. 但是, 不知道P ＝ NP。看来你可以在多项式时间内验证并生成NP类中的基于决策的问题集, 这是不可能的, 因为根据NP类的定义, 你可以在多项式时间内验证解。因此, 这种关系永远无法保持。

简化

NP类完全（NPC）问题由一组决策问题（NP类的子集）组成, 没人知道如何有效解决。但是, 即使对于单个NP完全问题都有多项式解, 那么NPC中的每个问题都将在多项式时间内得到解决。为此, 我们需要减少的概念。

假设存在两个问题A和B。你知道不可能在多项式时间内解决问题A。你想证明B不能在多项式时间内解释。我们想证明（A∉P）=>（B∉P）

请考虑一个示例来说明还原：众所周知, 以下问题是NPC：

3色：给定图G, 可以用3种不同颜色之一标记其每个顶点, 以使两个相邻的顶点没有相同的标签（颜色）。

在各种分区问题中会出现着色, 其中存在不能将两个对象分配给同一分区集合的约束。短语“着色”来自于地图绘制中的原始应用程序。有两个共同边界的国家应涂上不同的颜色。

众所周知, 平面图可以用四种颜色着色（映射）。为此, 存在多项式时间算法。但是很难确定是否可以使用3种颜色完成此操作, 并且没有多项式时间算法。

图：3色和非3色图形的示例。

多项式时间减少

我们说, 如果存在一个多项式时间计算函数f, 当且仅当xϵL2时, x等于LϵL1, 所以决策问题L1是多项式时间可简化为决策问题L2（L1≤pL2）。