P vs NP 实际上是什么
What P vs NP is actually about
频道:Polylog · 时长:17:57 · 发布:2024-08-19 · 播放:278162
简介
Polylog 解释了如何将算法转化为电路并编码为可满足性问题,从而有效地反向运行它们。它以此引出破解 RSA、对 SAT 的一般归约,以及 P vs NP 真正在问什么。
HN 为什么推荐
推荐为对 P vs NP 的直观、动画解释,围绕反转计算展开。
我强烈推荐观看 — HN, 2024
中文字幕节选
有没有想过我们能让计算机倒着运行? 今天我们将从一个不同寻常的角度,来看看计算机科学中最著名的问题, P vs NP。 看完这个视频,你就会明白为什么 P vs NP 问题 归根结底是在问我们能否反转算法。 首先,我们来认识可满足性问题,简称 SAT,它堪称算法问题中的 超级英雄。 我们知道它有着成千上万种等价的定义,而我们 至今仍不知道如何求解它。 接下来,我们将通过构建一个乘法电路,并利用 SAT 让它反向运行, 来破解一个著名的密码。 最后,我们将看到反转算法的思想如何与 计算机科学中最重要的 P 与 NP 问题联系起来。 我们的故事从可满足性问题开始,它也被称为 SAT。 这是一个极其强大的问题。 我们将看到,如果我们能高效地求解它,就能 用它来反转任何算法。 让我们来看看这个问题到底是什么。 给定一组布尔变量,也就是说每个变量都可以 被设为真或假。 但既然我是个程序员,我就用 1 和 0 来表示。 我们还给定了一组关于这些变量的逻辑约束, 这些约束必须被满足。 在一般的 SAT 问题中,约束可以是任意 复杂的逻辑公式,就像这样。 但为了简单起见,我们只考虑所谓的 CNF SAT。 在这个变体中,每个约束是一组变量或其 否定,用 OR 连接起来。 比如,这个约束表示要么 b 必须是 1, 要么 c 必须是 0,要么 d 必须是 0。 任务是给变量赋值,使得所有约束都被满足。 这组特定的取值是可行的,因为如果我们把这些值代入 约束并化简,每个约束都求值为 1,也就是说被满足了。 给定一个大型可满足性问题,求解它,或者判断出 它无解,是一个非常困难的计算问题。 但让我们做这样一个思想实验。 假设我们确实有一个非常快的 SAT 求解器。 这样的算法会带来什么有趣的推论吗? 答案是,它会彻底摧毁我们对宇宙的 一切直觉。 先从冰山一角说起,让我们看看如何用这个 快速 SAT 求解器来破解也许是最著名的密码——RSA。 RSA 密码的安全性建立在这样一个假设之上:因数分解, 即把一个合数写成两个整数的乘积,是一个 非常困难的计算问题。 据我们所知,情况确实如此,但如果我们有一个非常快的 SAT 求解器, 我们就能突然解决因数分解问题。 让我们看看为什么。 首先,我们来谈谈因数分解的逆问题——乘法。 假设你想把两个非常大的数相乘,比如 3 和 5。 我们可以把这个问题归约到 SAT。 我们将利用你在学校学过的长乘法算法。 你学的是十进制数的版本,但我们将用二进制。 那么让我们把数字 3 和 5 转换成二进制,然后运行这个算法。 我们先计算中间乘积,然后把它们加起来。 要把这个算法转换成 SAT 实例,我们将把它 看作一个所谓的电路。 电路就是一堆可以传播信号的导线,以及 施加简单逻辑函数的门。 你可以把每个输入导线的值固定为 1 或 0。 然后信号通过导线和门传播,你可以在末端
HN 上的讨论
尽管整篇文章都提到了,但我没有看到相关视频的链接。几周前它发布时我看到了,非常喜欢。我强烈推荐观看,尤其是如果你对P vs NP的影响还不熟悉的话[1] [1] [VIDEO] — nick_g, 2024-10
是的,这是一个很好的补充。我认为我们使用的词语常常会让事情变得更加混乱。比如我讨厌人们说可逆,但指的是一个不是双射的函数。为什么不说可反向呢?(对像/原像的约定没有抱怨)这与说“单向”造成的问题非常相似。它并不是单向的。往另一个方向走是完全可能的,但找到起源却极其困难。我喜欢用来向人们解释的视觉隐喻是,就像你走出一个房间,进入一个所有门看起来都一样的走廊。忽略你可以直接转身的事实,要弄清楚你实际上是从哪扇门出来的会非常困难。但也许我最不喜欢的是,我们最终为同一个一般概念有了这么多术语。当它们是独立发现的时候是一回事,但我很确定开创哈希的计算机科学家们对数学和命名法相当熟悉。> 逆向计算将需要难以处理的时间。真正附带说一句,我非常喜欢这个对P vs NP的解释,因为它明确地讨论了可逆性。[VIDEO] — godelski, 2026-02
> 计算具有方向性意味着什么?实际上,所有计算都具有方向性!这实际上是一个让我非常兴奋的话题 ^__^ 想想看,我们有一个函数 f,输入 x,输出 y。f(x) -> y 我们甚至会使用这种表示法!这就是我们的方向。现在,反过来实际上有点棘手。如果反向是直接的,我们的函数就有逆函数。但可能并不总是如此。所以我们的函数 f(x)=mx+b 是可逆的,因为我们可以写成 x = (f(x)-b)/m(嗯... m 不能为 0),这提供了唯一解。每个 x 对应唯一的 f(x)。但如果相反,我们有函数 f(x) = x^2,这就不成立了!x = sqrt(f(x)),这里每个 f(x) 对应 x 和 -x!它们不是唯一的。如果你想开始走这条路,我们可以开始采用像和原像的语言。这里有很多有趣的现象,如果你还没猜到,是的,这与 P=NP 问题有关!一个直观的方法是写下计算电路。Polylog 实际上有… — godelski, 2025-06
嗨,我是这篇博客文章的作者。1)我和其他人一起制作高投入的YouTube视频,我们的频道叫Polylog。我们最近制作了一个关于P vs NP的一个被低估的观点的视频。[1] 2)在制作高投入视频之后,我总是写一篇低投入、意识流风格、非常未编辑的博客文章,在其中澄清一些细节或解释一些更晦涩的内容,这些内容没有进入视频。你正在讨论的博客文章就是这样的。所以你应该先看视频,只有当你真的很喜欢视频并想了解更多时,才阅读博客文章。:) 3)如果你有任何问题,我很乐意回答![1] [VIDEO] — vasekrozhon, 2024-10
[VIDEO] 我认为这个视频以一种非常直观的方式说明了为什么这是真的。几天前我把它作为链接发布,但从未引起关注。SAT等价于能够找到任何函数的逆,因为你可以用逻辑门描述任何函数(原因很明显),而任何描述函数的逻辑门集合都等价于一个SAT问题。你需要做的就是将函数编码为逻辑门,包括你想要的输出,然后让SAT求解器找到产生该输出的输入。 — empath75, 2024-10
相关视频
- 这个高铁项目对美国是一个警告 · Vox · 8:25
- 动画投票方法 · Unify The Vote · 6:18
- 我们的投票制度(以及排序复选制)如何背叛你最喜欢的候选人 · The Center for Election Science · 3:34
- 更难的硬盘:我们不想要也不需要硬盘 · suckerpinch · 36:46
- 专业 SMT 焊接:手工焊接技术 - 表面贴装 · John Gammell · 3:19
- 贝叶斯定理:信念变化的几何学 · 3Blue1Brown · 15:11
- 为什么素数会形成这些螺旋?| 狄利克雷定理和圆周率近似 · 3Blue1Brown · 22:20
- John Cleese 对决极端主义 · eroosters · 2:12
- 战争的未来及其如何影响你(多域作战)- Smarter Every Day 211 · SmarterEveryDay · 28:11
- 第一讲 | 理论最小值 · Stanford · 1:46:33
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- CppCon 2017: Matt Kulukundis “逐步设计一个快速、高效、缓存友好的哈希表” · CppCon · 59:33
- 快速傅里叶变换(FFT):史上最巧妙的算法? · Reducible · 28:23
- 现代字典 by Raymond Hettinger · SF Python · 1:07:41
- 28c3:不安全性的科学 · 28c3 · 59:23
- Philip Wadler 的“命题即类型” · Strange Loop Conference · 42:43