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

相关文章

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模