P vs. NP 与计算复杂性动物园
P vs. NP and the Computational Complexity Zoo
频道:hackerdashery · 时长:10:44 · 发布:2014-08-26 · 播放:3701963
简介
一个 11 分钟的动画介绍 P vs. NP 以及更广泛的复杂性类图景,灵感来自 Complexity Zoo 维基。它假设读者没有计算机科学背景。
HN 为什么推荐
HN 反复推荐它作为对没有背景的人介绍 P vs. NP 和复杂性类的最佳简短、有趣的入门。
这个 10 分钟的视频是对 P = NP 问题和计算复杂性理论的绝佳介绍,如果你没有背景知识的话。 — HN, 2016
中文字幕节选
今天我想谈谈计算机科学中悬而未决的最深奥问题, 也许还是整个数学领域中最深奥的问题。 这个问题叫做P与NP。 我还想谈谈计算领域的理念 如何体现在我们周围的日常世界中,以及看似毫不相干的问题,比如 蛋白质折叠和制作填字游戏, 如何共享一个共同的核心难点,而这个难点其实很像数独,嗯, 好吧,基本上就是数独。 2000年,克莱研究所为 数学中七个关键问题的解答各悬赏100万美元—— 千禧年大奖难题。 这些都是深奥而困难的问题,而且对 其中大多数问题来说,光是理解问题本身就需要大量专业知识。 在这七个问题中,P与NP既是最近才提出的——1971年, 也是迄今为止最容易理解和解释的一个。 2010年3月,克莱研究所颁发了 七个奖项中的第一个,奖励的是——没错,不是P与NP——的解答。 那么,P与NP问题到底是什么? 嗯,早在20世纪70年代,计算机科学家们 正忙着研究如何给他们的 复古炫酷、柜子大小的计算机编程,以解决世界上所有的问题。 有时候,对于某个特定问题,人们能想到的第一个程序 会慢得没法用, 但后来,随着时间推移,人们会想出巧妙的方法让它更快, 或者至少,有些问题确实如此。 对于另一些问题,没人能想出更快的程序。 为了理清这种局面,他们开始 根据程序解决问题的速度,把问题分门别类。 对于乘法这样的问题,他们有非常快的程序, 而对于另一些问题,比如下绝对完美的国际象棋, 他们发现根本就不存在快速程序。 但对于中间的一大堆问题,他们不确定是否存在快速的解决方法。 于是,他们不断尝试。P和NP就是在这里登场的。 先跳过大量细节,P是一个类, 基本上包含了所有能由 相当快的程序解决的问题,比如乘法或按字母顺序排列名单。 然后,围绕着并包含P,我们发现了另一个类,叫做NP。 它包含所有这样的问题:如果给你一个正确的解答, 你至少能在合理的时间内检验它。 NP简直让人抓狂,因为它包含许多重要问题,比如 车辆路径规划、调度、电路设计和数据库。 而且,我们常常很幸运地发现某个NP问题其实属于P, 这样我们就有了快速程序。 但是,对于其中很多问题,这似乎并没有发生。 于是人们开始琢磨,NP中的所有问题是否最终都会属于P, 还是说有些NP问题确实比P中的问题更难。 这就是P与NP问题。 如果所有NP问题真的都属于P,那么 我们一直在苦苦挣扎的许多重要难题 对计算机来说都会变得很容易解决。 与生物学和治愈癌症相关的难题;商业和经济领域的难题。 我们几乎会在一夜之间得到许多奇迹般的答案。 而且我们用于网上银行等用途的加密也会很容易被破解, 因为它正是基于NP问题的。 好,举个例子: 我喜欢把NP中的问题基本上看作“谜题”, 因为我认为,谜题之所以是谜题,就在于 它是一个你可以直接给出答案的问题,而这就是NP的含义。 就像数独一样。 数独谜题可能要花很长时间才能解出,但如果我给你一个已经解好的数独网格,
HN 上的讨论
这是我最喜欢的相关概述——视频不仅解释了这些空间,还将其与对现实本身的一种理解联系了起来![VIDEO] — sgrove, 2023-05
有一个很棒的视频,每当我对它有点不确定时就会翻出来看看,强烈推荐——[VIDEO] — sgrove, 2017-12
> 我猜P!=NP的证明会是一个例子。不幸的是,它没有任何普通人能理解的简单描述。“难。真的很难。别开玩笑了。”现在在纸上回溯两个小例子。哦,看,这里的步数在增长,但这些增长得更快!尤其是数学,向普通人解释时很大程度上取决于所使用的语言。如果能设法在解释中避开复杂性动物园[1]的其余部分,并投入时间讲解非常基本的例子,很多原本普通人无法理解的东西都可以解释清楚。[1] [LINK] 编辑:在寻找上周偶然看到的那个对P vs NP有非常简洁解释的视频(我没再找到)时,我发现了这个:对普通人来说不算简单,但非常有趣,而且粗略地展示了P vs NP之外的东西,即复杂性动物园:[VIDEO](10分钟) — jlg23, 2017-06
我以前工作的一家公司里有个人做了一个很棒的相关视频。即使没有任何背景知识也能很容易理解:[VIDEO] — d23, 2017-01
如果你完全没有背景知识,这个10分钟的视频是了解P = NP问题和计算复杂性理论的绝佳入门。我给很多朋友看过(包括非计算机科学专业的)。本质上就是:“能够快速识别正确答案,是否意味着也存在快速找到答案的方法?” [VIDEO] — austinl, 2016-11
相关视频
- 编译和优化脚本语言 · Google TechTalks · 1:01:37
- Lucas Cavalcanti 与 Edward Wible - 探索 Datomic 的四个隐藏超能力 · ClojureTV · 40:42
- 反向模拟 NES,赋予它超级能力! · suckerpinch · 22:21
- RustLatam 2019 - Without Boats:零成本异步 IO · Rust Programming Language · 32:24
- APL中的康威生命游戏 · Dyalog · 7:47
- RSA动画:改变教育范式 · Royal Society of Arts · 11:40
- 实用 Common Lisp · Google TechTalks · 1:12:09
- 向量 | 第1章,线性代数的本质 · 3Blue1Brown · 9:51
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- 但什么是傅里叶变换?视觉介绍。 · 3Blue1Brown · 19:41
- 但什么是神经网络?| 深度学习第一章 · 3Blue1Brown · 18:40
- 贝塞尔曲线之美 · Freya Holmér · 24:25
- 样条曲线的连续性 · Freya Holmér · 1:13:50
- Jim Simons(完整版访谈)- Numberphile · Numberphile2 · 1:00:43
- 但比特币究竟是如何运作的? · 3Blue1Brown · 25:15
- 微积分的本质 · 3Blue1Brown · 17:04