多项式时间验证

本文概述

在讨论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)。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?