news 2026/8/24 15:48:15

p和np问题

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
p和np问题

p类问题表示,提供一种算法,不管问题里数据多么庞大,用这个算法消耗的时间不会巨量增加
比如你参加非诚勿扰,有100个女嘉宾和10000个女嘉宾给你选,如果规则是,选一个你最喜欢的带走,那你的算法只需要从第一个开始,一个一个比较,让你认为最漂亮的继续和下一个比较直到最后一个,这样比较的算法不会因为女嘉宾数量多,让你比较次数巨量增加
np类问题就是相反,数据稍微增加,时间消耗就增加得很恐怖,但是你却可以有一种算法,容易验证问题的答案是否正确
比如密码,只看英文字母,一位数的密码需要26次尝试,两位数却需要26*26,那平常用的10位那种呢?还不止英文字母,但是这类问题很容易验证正确与否,比如你的密码是123456,你用了123455,一下就可以知道是错的,回到p类,问题,我在10000个女嘉宾里问你,第245位女嘉宾是你最喜欢的,你觉得你认同我的这个答案么?所以p类问题还有个特点就是,没法迅速验证
为什么说p和np不能相等或者至少目前无法验证相等,还是刚才两个例子,女嘉宾和密码的问题
假如p和np相等,那么,这个世界就乱了
女嘉宾的问题:世界上存在一种算法,可以给你一个女嘉宾,你立刻知道是不是你最喜欢的,换句话说,假如我给了你正确的那个女嘉宾或者相亲时给你推荐正确的那个(别问我为什么知道正确的,因为我同样可以知道你的正确的密码,这样可以理解吧?),那么你立刻就找到了真爱,那相亲的意义何在?世界上就不会有那么多纠结的爱情故事,也许你会说,这很好啊,那就来看看密码问题
密码的问题:有一种算法,我不需要用大量的时间或者次数就可以得到你的密码,比如,一位密码需要26次,两位密码需要26+26次(当然这里在数学上是错的,可这符合p类问题里女嘉宾比较的规律),那么你的平时用的10位密码是260次,这下知道了吧?光是人类就可以轻松试出正确的密码,那这个世界还有安全可言么?
所以,p和np不能相等,或者说,至少目前不能找到这样的算法让两者互相转化
而且,找到转化的方法就像找到真爱一样让人憧憬和兴奋,又像泄露密码一样让人恐慌

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/8/24 15:40:51

带货视频生成工具全流程项目复盘

我们是服务家居类中小商家的代运营小团队,一共4个人,岗位分别是素材策划、剪辑、投放对接、品控,我是团队里的素材策划岗。之前连续两周我们卡在了上新季的千川带货素材产能缺口上,每周要出30条不同版本的15秒短视频,纯…

作者头像 李华
网站建设 2026/8/24 15:30:12

Linux下Nvidia显卡风扇控制:从底层原理到systemd服务实战

1. 项目缘起:为什么要在Linux下折腾显卡风扇?如果你在Linux系统下用过Nvidia的独立显卡,尤其是用来跑深度学习训练、科学计算或者玩一些游戏,大概率会遇到一个让人头疼的问题:显卡风扇要么像疯了一样狂转,噪…

作者头像 李华
网站建设 2026/8/24 15:29:54

华为OD机试:数列计算与斐波那契优化实战

1. 项目背景与需求解析 华为OD(Huawei Outsourcing Development)机试是华为技术有限公司面向外包开发人员设计的编程能力测评系统。2026年4月1日更新的机试真题中,"计算数列位置N的值"作为典型算法题出现,考察应聘者对基…

作者头像 李华
网站建设 2026/8/24 15:28:45

QModMaster:ModBus 调试工具使用指南

QModMaster:ModBus 调试工具使用指南 【免费下载链接】qModbusMaster Fork of QModMaster (https://sourceforge.net/p/qmodmaster/code/ci/default/tree/) 项目地址: https://gitcode.com/gh_mirrors/qm/qModbusMaster 它是什么,能干什么 QModM…

作者头像 李华