P、NP、NP-hard、NPC问题超简单理解

2024-04-01 05:48
文章标签 简单 问题 理解 np hard npc

本文主要是介绍P、NP、NP-hard、NPC问题超简单理解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

查了好多资料,现在网上的资料都不说人话,简单的问题故意写得让别人看懂不以显示自己的水平很高深?真正的大师难道不是把复杂问题说得很简单的人?把简单问题说得让别人看不懂显得自己很高深的就是煞笔。

多项式定义:就是一元N次方式,时间复杂度为多项式的问题都很容易解出来

各类问题关系图: (结合以下文字说明看)
在这里插入图片描述

问题定义:

  1. P问题:一个问题可以在多项式(O(n^k))的时间复杂度内解决(简单的问题);
    例如:n个数的排序问题(不超过O(n^2))

  2. NP问题:一个问题的解可以在多项式的时间内被证实或证伪,即给出一个答案,可以很快地(在多项式时间内)验证这个答案是对的还是错的,但是不一定能在多项式时间求出正确的解;
    例如: 背包客问题,任何一条路线方案都可以很快地被计算代价,但是无法在多项式时间内求出最优解。

  3. NP-hard问题:假设存在这样一个问题,1)任意np问题都可以在多项式时间内归约为该问题;2)解决了该问题就解决了NP问题;这个问题就是NP-hard问题;
    即为了解决问题A,先将问题A归约为另一个问题B,解决问题B同时也间接解决了问题A。问题B就是一个NP-hard问题;
    范围: 无多项式时间求解算法且不一定能在多项式时间内验证解的问题
    例如,停机问题。

  4. NPC问题:**理解一:**如果存在一个问题可以在多项式时间内验证解的正确性,其他问题也可以归约为该问题,解决了该问题就解决了NP问题,该问题就是NPC问题。
    理解二: 存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。其定义要满足2个条件: 1) 首先,它得是一个NP问题;2) 然后,所有的NP问题都可以约化到它。
    要证明npc问题的思路就是:
    先证明它至少是一个NP问题,再证明其中一个已知的NPC问题能约化到它。
    范围: NPC问题既是NP问题,也是NP-hard问题。
    例如,SAT问题(第一个NPC问题)。该问题的基本意思是,给定一系列布尔变量以及它的约束集,是否存在一个解使得它的输出为真。

参考文献:
1.https://blog.csdn.net/qq_21768483/article/details/80430590
2.https://www.zhihu.com/question/27039635

这篇关于P、NP、NP-hard、NPC问题超简单理解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/866353

相关文章

MySQL启动报错:InnoDB表空间丢失问题及解决方法

《MySQL启动报错:InnoDB表空间丢失问题及解决方法》在启动MySQL时,遇到了InnoDB:Tablespace5975wasnotfound,该错误表明MySQL在启动过程中无法找到指定的s... 目录mysql 启动报错:InnoDB 表空间丢失问题及解决方法错误分析解决方案1. 启用 inno

Java使用MethodHandle来替代反射,提高性能问题

《Java使用MethodHandle来替代反射,提高性能问题》:本文主要介绍Java使用MethodHandle来替代反射,提高性能问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录一、认识MethodHandle1、简介2、使用方式3、与反射的区别二、示例1、基本使用2、(重要)

电脑蓝牙连不上怎么办? 5 招教你轻松修复Mac蓝牙连接问题的技巧

《电脑蓝牙连不上怎么办?5招教你轻松修复Mac蓝牙连接问题的技巧》蓝牙连接问题是一些Mac用户经常遇到的常见问题之一,在本文章中,我们将提供一些有用的提示和技巧,帮助您解决可能出现的蓝牙连接问... 蓝牙作为一种流行的无线技术,已经成为我们连接各种设备的重要工具。在 MAC 上,你可以根据自己的需求,轻松地

Java 中的跨域问题解决方法

《Java中的跨域问题解决方法》跨域问题本质上是浏览器的一种安全机制,与Java本身无关,但Java后端开发者需要理解其来源以便正确解决,下面给大家介绍Java中的跨域问题解决方法,感兴趣的朋友一起... 目录1、Java 中跨域问题的来源1.1. 浏览器同源策略(Same-Origin Policy)1.

如何清理MySQL中的binlog问题

《如何清理MySQL中的binlog问题》:本文主要介绍清理MySQL中的binlog问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目http://www.chinasem.cn录清理mysql中的binlog1.查看binlog过期时间2. 修改binlog过期

如何解决yum无法安装epel-release的问题

《如何解决yum无法安装epel-release的问题》:本文主要介绍如何解决yum无法安装epel-release的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录yum无法安装epel-release尝试了第一种方法第二种方法(我就是用这种方法解决的)总结yum

IDEA下"File is read-only"可能原因分析及"找不到或无法加载主类"的问题

《IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题》:本文主要介绍IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题,具有很好的参... 目录1.File is read-only”可能原因2.“找不到或无法加载主类”问题的解决总结1.File

idea中project的显示问题及解决

《idea中project的显示问题及解决》:本文主要介绍idea中project的显示问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录idea中project的显示问题清除配置重China编程新生成配置总结idea中project的显示问题新建空的pr

windows和Linux安装Jmeter与简单使用方式

《windows和Linux安装Jmeter与简单使用方式》:本文主要介绍windows和Linux安装Jmeter与简单使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录Windows和linux安装Jmeter与简单使用一、下载安装包二、JDK安装1.windows设

redis在spring boot中异常退出的问题解决方案

《redis在springboot中异常退出的问题解决方案》:本文主要介绍redis在springboot中异常退出的问题解决方案,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴... 目录问题:解决 问题根源️ 解决方案1. 异步处理 + 提前ACK(关键步骤)2. 调整Redis消费者组