个性化阅读
专注于IT技术分析

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。

NP完成度
赞(0)
未经允许不得转载:srcmini » NP完全问题实例分析

评论 抢沙发

评论前必须登录!