多项式时间验证多项式时间验证|算法设计与分

本文概述

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

在讨论NP完全问题的类别之前, 必须先介绍验证算法的概念。
许多问题很难解决, 但是它们具有以下特性：如果提供了解决方案, 则很容易对解决方案进行身份验证。
哈密??顿循环问题：考虑哈密顿循环问题。给定一个无向图G, G是否有一个循环访问每个顶点一次？此争议没有已知的多项式时间算法。
注意：-这意味着即使没有为具有特定顶点的哈密顿循环提供特定的路径, 也无法在具有多项式时间的图形中构建哈密顿循环, 但是你无法在多项式内验证哈密顿循环时间

文章图片
无花果：哈密顿周期
让我们了解一下, 图确实具有哈密顿循环。有人会很容易说服这一点。他们会类似地说：“时间段是hv3, v7, v1 … … v13i。
然后, 我们可以检查图并检查这确实是一个合法周期, 并且它恰好访问了图的所有顶点一次。因此, 即使我们不知道解决哈密顿循环问题的有效方法, 也存在一种有益的方法来验证给定的循环确实是哈密顿循环。
注意：-为了在无向哈密顿循环图G的多项式时间内进行验证。必须给出哈密顿循环的精确/特定/确定路径, 然后才能在多项式时间内进行验证。证书的定义：-包含在顶点给定路径中的一条信息称为证书
P和NP类的关系

NP中含有P
P = NP

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

简化 【多项式时间验证】NP类完全（NPC）问题由一组决策问题（NP类的子集）组成, 没人知道如何有效解决。但是, 即使对于单个NP完全问题都有多项式解, 那么NPC中的每个问题都将在多项式时间内得到解决。为此, 我们需要减少的概念。
假设存在两个问题A和B。你知道不可能在多项式时间内解决问题A。你想证明B不能在多项式时间内解释。我们想证明（A?P）=> （B?P）
请考虑一个示例来说明还原：众所周知, 以下问题是NPC：
3色：给定图G, 可以用3种不同颜色之一标记其每个顶点, 以使两个相邻的顶点没有相同的标签（颜色）。
在各种分区问题中会出现着色, 其中存在不能将两个对象分配给同一分区集合的约束。短语“着色”来自于地图绘制中的原始应用程序。有两个共同边界的国家应涂上不同的颜色。
众所周知, 平面图可以用四种颜色着色（映射）。为此, 存在多项式时间算法。但是很难确定是否可以使用3种颜色完成此操作, 并且没有多项式时间算法。