NP问题的通俗解释

本博客参考:

  • https://zhuanlan.zhihu.com/p/348250098
  • https://zhuanlan.zhihu.com/p/348020672
  • https://zhuanlan.zhihu.com/p/260512272
  • 以及相关的1-6。

是什么

NP的全称是Non Deteministic Polynomial,是线性所不能判别的问题的集合。

NP这个东西是从哪里来的呢?

起源

NP的提出,是基于图灵机模型的。

什么是图灵机?

图灵机有k条带子,左端有限,右端要多长可以有多长(潜在无限长)。每条带子都按顺序划分了格子,一个格子可以记录一个符号。符号的有限集我们称之为字母表(alphabet) . 每条带子上有一个带头(tape head),可以读取或更改一个格子里的内容。带头可以左右移动,我们规定图灵机的每个步骤中,带头只能向左一格、向右一格或不动。
在这里插入图片描述用最通俗的语言来解释,图灵机是运行在3条带子和寄存器上的符合规则的自动化的机器。

用图灵机解决问题

有了这个机器,怎样才算使用这个机器解决了问题呢?为了简洁,我们目前只限定“判别命题是否为真”这种判别类问题。

当对输入和问题,图灵机运算后,图灵机能停,并且输出判定结果,则称图灵机解决了此问题。

通俗理解,是对于一个命题,图灵机能够不死循环,并且输出判别结果是真是否,那么就说此问题被图灵机解决。

对图灵机的大胆猜测

强邱奇-图灵(CT)论题:任何物理上可实现的计算装置A,都可被图灵机以多项式代价模拟。

再换句话说,任何装置都可以别图灵机以多项式的代价模拟。

不过请注意,这是一个论题,不是结论,是一个猜想。
为了验证此猜想,其举例了三个装置,每一个装置都能用图灵机“代替”,三个装置分别是:1. 任意大的字母表;2.单带图灵机;3.双向图灵机。(感兴趣可以看原帖子,我们只需要理解,此猜想大胆认为任何装置都能被以线性代价图灵机模拟替代。)

图灵机的泛化

该泛化认为,任意一个装置/程序,都可以被看成一个“通用图灵机”,即输入-处理-输出。

以当前我们熟悉的东西举个例子,对于某一个单独的指令,一个主机可以被看成图灵机;一个手机可以被看成图灵机;以及一个程序,也可以被看成一个图灵机

对图灵机解决问题的复杂度

A reminder,“解决问题”的定义,是图灵机能够判断此命题是否为真。

结合C-T论题,我们把所有具有多项式时间算法的问题认为是同一类,也就是P (Polynomial)类。但凡在这类里面的问题,都被叫做在图灵机上有“高效算法”。

这其实也变相声明了图灵机的计算复杂度上限,是线性问题,也就是复杂度 O ( 1 ) 、 O ( n a ) 、 O ( l o g a ( n ) ) O(1)、O(n^a)、O(log_a(n)) O(1)O(na)O(loga(n)),其中 a a a是常数。

非确定性图灵机

刚刚我们所“熟悉”的图灵机,叫做确定性图灵机。还有一种,叫做非确定性图灵机。二者对比:
在这里插入图片描述
换一张:
在这里插入图片描述可以看到,左侧的情况下,对于计算的“搜索” 的效率,不如右侧的高。

这种非确定性的图灵机,通常用来解决存在性问题。NDTM的每一条计算路径试图构造一个存在性证明,若构造成功,在输出带上写1并停机,称该计算是成功的,该终止格局为接受格局;若构造失败,在输出带上写0并停机,称该计算是失败的,该终止格局为拒绝格局;永不终止的计算路径也视为失败的。

看到这里,目前所有的程序,都是左侧的图灵机的泛化,对于右侧的非确定性图灵机,还没有一个物理现实(不过好像量子计算机就是,但是还没实用)。在原帖中,对于非线性复杂度的问题,右侧的非确定性图灵机能够以线性复杂度解决。

所以出现了P类问题Polynomial,即能使用确定性图灵机有高效解决方法的问题;和NP问题Non deterministic Polynomial,不能用确定性图灵机线性判别的问题。

回到现在,网络上的帖子

看到很多视频或者回答说P问题就O()多少的问题,然后复杂度上到O多少,就是NP问题了。

确实说的也不能算错,就是这个NP出现的源头,其实算是说,有没有存在一个“高效算法”在当前这个问题上。

由于现在所有的程序都是确定性图灵机的泛化,所以对于非线性的复杂度问题是不存在“高效算法”的。现在大家也不说deterministic了,只说能否在合理时间下输出结果。这也算概念的引申吧!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用RabbitMQ

使用RabbitMQ 1 Docker安装RabbitMQ 1.1 安装RabbitMQ # 下载含有管理页面的镜像 docker pull rabbitmq:3.8.8-management# 创建容器 # 5672:应用访问端口;15672:控制台Web端口号; docker run -itd \ --namemy-rabbitmq \ --re…

第六章:YOLO v1网络详解(统一的实时目标检测)

(目标检测篇)系列文章目录 第一章:R-CNN网络详解 第二章:Fast R-CNN网络详解 第三章:Faster R-CNN网络详解 第四章:SSD网络详解 第五章:Mask R-CNN网络详解 第六章:YOLO v1网络详解 第七章:YOLO v2网络详解 第八章:YOLO v3网络详解 文章目录 系列文章目录技…

记录一个heatmap.js在strict模式下的bug

ImageData的data属性只读&#xff0c;无法修改 出问题的在原始代码的490行~528行 var img this.shadowCtx.getImageData(x, y, width, height);var imgData img.data;var len imgData.length;var palette this._palette;for (var i 3; i < len; i 4) {var alpha imgD…

springboot项目中引入本地依赖jar包,并打包到lib文件夹中

1.springboot项目中引入本地依赖jar包&#xff0c;并打包到lib文件夹中 描述&#xff1a;下载了第三方相关jar包后&#xff0c;项目中引入本地jar&#xff0c;测试环境正常&#xff0c;打包线上报错提示为找到该jar 原因&#xff1a;应该在/WEB-INF/lib/xxx.jar&#xff0c;被…

基于深度学习的高精度刀具检测识别系统(PyTorch+Pyside6+YOLOv5模型)

摘要&#xff1a;基于深度学习的高精度刀具检测识别系统可用于日常生活中或野外来检测与定位刀具目标&#xff0c;利用深度学习算法可实现图片、视频、摄像头等方式的刀具目标检测识别&#xff0c;另外支持结果可视化与图片或视频检测结果的导出。本系统采用YOLOv5目标检测模型…

当你按下键盘A键

CPU 里面的内存接口&#xff0c;直接和系统总线通信&#xff0c;然后系统总线再接入一个 I/O 桥接器&#xff0c;这个 I/O 桥接器&#xff0c;另一边接入了内存总线&#xff0c;使得 CPU 和内存通信。再另一边&#xff0c;又接入了一个 I/O 总线&#xff0c;用来连接 I/O 设备&…

前端框架Layui的使用讲解(Layui搭建登录注册页面)

目录 一、前言 1.什么是Layui 2.Layui的背景 3.为什么要使用Layui 4.Layui的模块化 二、Layui使用讲解 1.初识Layui 2.搭建登录页面 静态效果图​ 封装引入文件页面&#xff08;公用页面&#xff09; jsp页面搭建 userDao编写 Servlet页面编写 xml文件配置 3.搭…

DAY41:贪心算法(十)监控二叉树

文章目录 968.监控二叉树思路遍历顺序空节点处理情况列举 最开始的写法debug测试&#xff1a;travelsal的输出多了1 修改版二叉树注意点时间复杂度总结 968.监控二叉树 给定一个二叉树&#xff0c;我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及…

​python接口自动化(三十一)--html测试报告通过邮件发出去——下(详解)​

简介  本篇总结了 QQ &#xff08;SSL&#xff09;邮箱和 163&#xff08;非SSL&#xff09; 邮箱发送邮件&#xff0c;专治各种不行&#xff0c;总之看完这篇以后麻麻再也不用担心我的邮件收不到了。以下代码兼容 python2 和 python3&#xff0c;运行无异常&#xff0c;放心大…

语义分割大模型SAM论文阅读(二)

论文链接 Segment Anything 开源代码链接 SAM 论文阅读 摘要 We introduce the Segment Anything (SA) project: a new task, model, and dataset for image segmentation. Using our efficient model in a data collection loop, we built the largest segmentation dat…

Vue数据项加圆点

目录 Html 样式 方法 Html <el-table-column prop"status" label"数据状态" header-align"center" width"200"><template slot-scope"scope"><div style"display: flex; justify-content: center; a…

fun函数方法体=返回值,kotlin

fun函数方法体返回值&#xff0c;kotlin var str: String "fly"fun main(args: Array<String>) {println(getMyString())println(getMyInt())str "phil"println(getMyString())println(getMyInt()) }fun getMyInt(): Int {return if (str.equals(&…

使用OpenCV在图像上绘制质心

这段代码中已经实现了在图像上绘制质心的功能。质心,也称为重心,是物体质量分布的几何中心,可以通过物体质量和位置的加权平均来求得。 在这个程序中,图像的质心(重心)是通过计算像素强度(可以被看作是“质量”)的加权平均位置得到的。图像上每一个像素都有一个位置(…

搭建SpringBoot项目 详细教程

一、搭建SpringBoot项目 这个项目&#xff0c;可以作为种子项目&#xff0c;我打算把它放置Gitee上。包含大部分web开发的相关功能&#xff0c;后期所有的Spring Boot项目都可以用这个项目&#xff0c;简单修改一下配置&#xff0c;就可以快速开发了。 选择Spring initializr…

【Java】链表LinkedList

文章目录 一、链表1.1 链表的概念1.2 链表的结构 二、LinkedList的简介三、LinkedList的使用3.1 构造方法3.2 常见操作3.3 遍历方法 四、LinkedList的模拟实现五、LinkedList 和 ArrayList 的区别 一、链表 1.1 链表的概念 链表&#xff08;Linked List&#xff09;是一种常见…

预付费智能水表远程控制系统

预付费智能水表远程控制系统是一种基于物联网技术的智能水表管理系统&#xff0c;它通过远程通信技术和云计算平台&#xff0c;实现了对水表的实时监控、数据采集、费用计算、远程控制等功能。该系统不仅可以提高水务公司的管理效率&#xff0c;还可以为用户提供更加便捷、可靠…

Todo-List案例版本二

(160条消息) Todo-List案例版本一_bubbleJessica的博客-CSDN博客 引入了localStorage&#xff0c;让案例更加完善 src/App.vue <template><div id"root"><div class"todo-container"><div class"todo-wrap"><MyHe…

emacs下相对行号的设置

全局设置 全局开启行号显示&#xff1a;global-display-line-numbers-mode t 并设置 display-line-numbers-type的样式: relative 相对 配置代码如下: (use-package emacs:ensure t:config (setq display-line-numbers-type relative) (global-display-line-numbers-mode t)…

TypeScript 学习笔记(三):函数

一、函数定义 函数是由一连串的子程序&#xff08;语句的集合&#xff09;所组成的&#xff0c;可以被外部程序调用&#xff0c;向函数传递参数之后&#xff0c;函数可以返回一定的值。 通常情况下&#xff0c;TypeScript 代码是自上而下执行的&#xff0c;不过函数体内部的代…

SELECT * 会导致查询效率低的原因

SELECT * 会导致查询效率低的原因 前言一、适合SELECT * 的使用场景二、SELECT * 会导致查询效率低的原因2.1、数据库引擎的查询流程2.2、SELECT * 的实际执行过程2.3、使用 SELECT * 查询语句带来的不良影响 三、优化查询效率的方法四、总结 前言 因为 SELECT * 查询语句会查…
最新文章