NP完全问题实例分析

本文概述

• 简化和分解
• NP完全问题的例子

判定问题L为NP-Hard

对于所有L’NP, L’≤pL。

定义：如果L是NP完全的, 则

1. LϵNP和
2. 对于某些已知的NP完全问题L, L’≤pL。给定这个正式定义, 复杂度类为：

P：是可以在多项式时间内解决的一组决策问题。

NP：是一组可以在多项式时间内验证的决策问题。

NP-Hard：如果对于所有L’NP, L’≤pL, 则L是NP-hard。因此, 如果我们可以在多项式时间内求解L, 则可以在多项式时间内求解所有NP问题。

如果NP-Complete L是NP-complete

1. LϵNP和
2. L是NP-hard

如果可以在多项式时间内解决任何NP-完全问题, 那么每个NP-Complete问题也可以在多项式时间内解决。相反, 如果我们可以证明不能在多项式时间内解决任何NP-Complete问题, 则每个NP-Complete问题都无法在多项式时间内解决。

简化和分解

概念：-如果不存在NPC问题的解, 则在多项式时间内从一个NPC问题转换为另一个NPC问题。为此, 你需要减少的概念。如果在多项式时间内存在一个NPC问题的解决方案, 那么其余问题也可以在多项式时间内给出解决方案（但很难相信）。为此, 你需要减少的概念。

示例：-假设存在两个问题A和B。你知道不可能在多项式时间内解决问题A。你想证明B不能在多项式时间内求解。因此, 你可以在多项式时间内将问题A转换为问题B。

NP完全问题的例子

NP问题：-假设提供了基于决策的问题, 其中一组输入/高输入可以得到高输出。

NP硬性或NP完整性的标准。

1. 这里要注意的一点是, 已经给出了输出, 你可以在多项式时间内验证输出/解, 但不能在多项式时间内产生输出/解。
2. 这里我们需要简化的概念, 因为当你不能根据给定的输入生成问题的输出时, 如果你不得不强调简化的概念, 则可以将一个问题转换为另一个问题。

注意1：-如果你同时满足上述两点, 那么你的问题就属于NP-完全课程

注意2：-如果你仅满足第二点, 则你的问题属于NP困难类别。

因此, 根据给定的基于决策的NP问题, 你可以采用yes或no的形式进行决策。如果是, 那么你必须进行验证, 并通过简化概念将其转换为另一个问题。如果你正在执行任务, 则基于决策的NP问题都将在NP中竞争。

在这里, 我们将强调NPC。