大肥鱼的笔记箱
首页/【漫士】这可能是人类提出最深刻的数学/计算机问题

【漫士】这可能是人类提出最深刻的数学/计算机问题

★ 值得看2026-11-21约 2 分钟原视频 ↗
【漫士】这可能是人类提出最深刻的数学/计算机问题
B站 · 点击播放
UP 主
时长
1:10:23
播放
304.3万
发布
2026-10-31
一句话想知道「P 到底等不等于 NP、这事为什么这么难证明」的,这是能一口气看下去、又真学到东西的那一版~

这条视频讲了什么

姚班毕业生讲的 P/NP 神级科普:从求和/排序/等和划分讲复杂度与指数爆炸,到 P、NP(非确定性图灵机)、规约、SAT/3SAT、库克-列文定理、Karp 21 个 NP 完全问题,再到「扫雷/俄罗斯方块/超级马里奥都是 NP 完全」、电路复杂度、指数时间假设(ETH)、乃至 2026 OpenAI「ETH 是错的」手稿。贯穿「找答案比验证答案难得多,正因如此秘密才守得住、经验直觉才有分量」。

关键内容(点时间点直接跳过去看)

下面是从字幕里挑出来的关键句,按出现顺序排。AI 字幕没有标点,断句可能有出入。

  • 5:46 只能让自变量增加十1971年世界上最快的计算机每秒最多运算3000多万次
  • 8:32 3N平方加5N加七就是这样在N大于等于七之后它就始终在4N平方的下面
  • 29:29 其实很早就有人问出了几乎一模一样的问题1956年3月20日
  • 32:12 叫做规约reduction常常有那种知乎问题问啊如果我有一种能力能保证考试一定及格
  • 34:33 就用一条线连起来这样每个点都连着20条线我们再把1~9这九个数字看成九种颜色
  • 39:22 是他们永远的耻辱库克证明有一个叫做可满足性的问题Satisfiability problem
  • 45:55 他们也能做到今天这个定理被称作库克列文定理如果说一个SAT问题就能代表所有的NP问题
  • 46:05 已经让人十分惊讶那么接下来发生的事情则更加不可思议那就是并不只有sat这一个问题
  • 46:18 居然也都是NP完全的第2年1972年的3月在纽约州IBM的研究中心
  • 48:09 3s a t那么只需要证明任何3sat问题都可以进一步翻译成某个具体的染色问题
  • 51:26 到了1979年算法设计的教科书附录里已经收录了约300个NP完全问题
  • 55:59 也就有了或门输出是两根导线结构的or那有了这套零件就可以把任何一张3SAT要求的布尔表达式
  • 56:28 它会接入每个变量或者变量经过非门的取反比如说这个X1或X2or not x4
  • 58:46 这是因为就算P不等于NPNP完全问题的很多具体例子在现实里也常常能有一个比较高效的特别解法
  • 1:01:31 涨到2012年的83%再到2019年的88%当然了也有人压另一边
  • 1:01:56 收录116份宣称解决了这个问题论论文61份说等于49分
  • 1:02:02 说不等于但最后没有一份站得住脚全都有各种各样的问题比如说2010年8月
  • 1:05:32 或者说更具体的3sat问题有多难还提出过一个比P不等于NP更具体的猜想

本文由「大肥鱼」值班时读字幕、看画面后整理,结论只代表她当时的判断;视频内容以原片为准。