P/NP问题50年：基础理论举步维艰，但AI正在不可能中寻找可能

加星标，才能不错过每日推送！方法见文末动图

翻译 | 许钊箐

致谢

特别提示

长按下方图片关注「返朴」，查看更多历史文章

微信实行乱序推送，常点“在看”，可防失联

核心观点：

3. 虽然P/NP问题一开始涉及复杂问题的计算求解，但如今我们将其视为绘制这个领域未来发展蓝图的一种方法。

（编者注：正文内参考文献序号为原文标注；原文发表于2022年。）

撰文 |

Lance Fortnow

^[13]

^[38]

^[8]

^[21]

P/NP 问题

不存在

^[13]

^[14]

^[16]

为什么我们现在谈论P/NP问题？

^[10]

^[23]

^[27]

乐观之地（Optiland）

在1995年的一篇经典论文中^[20]，拉塞尔·因帕利亚佐（Russell Impagliazzo）描述了对于P/NP问题拥有不同程度可能性的五个世界：

1. 算法世界（Algorithmica）：P=NP或者某种理论上的等价，比如NP问题的快速随机算法。

2. 启发世界（Heuristica）: 在最坏的情况下NP问题很难求解，但是通常情况下求解是容易的。

3. 悲观世界（Pessiland；译者注：引申自拉丁语悲观主义pessimus）：我们可以轻易地构建难以求解的NP问题，但是很难构建我们知道解答的NP问题。这是所有可能性中最坏的，因为在这个世界中，我们既不能在通常情况下解决困难的问题，也不能由这些问题的难度获得任何明显的加密优势。

4. 单向加密世界（Minicrypt）：单向加密函数存在，但是我们没有公开密钥加密算法。

^[13]

困难问题的求解

^[9]

^[7]

数据科学与机器学习

^[28]

^[26]

通用分布（Universal distribution）和GPT-3

^[25]

^[5]

科学与医药

^[22]

P/NP之外：象棋与围棋

^[11]

^[35]

^[33]

可解释的人工智能 很多机器学习算法似乎已经都运行得很好，但是我们却不理解为什么。如果你去观察为了语音识别而训练的神经网络，你通常会难以理解它为何做出这样的选择。我们为什么要关心这个问题呢？以下是一些原因：

1. 置信：我们如何知道神经网络运行正确？除了检查输入和输出，我们不会做其他任何的分析。不同的应用场景会有不同的置信水平：Netflix推荐了一部水平不高的电影没什么关系，但如果是自动驾驶的汽车选择了一个错误的转弯，结果就很严重。

2. 公平：有很多例子表明，通过数据训练的算法受到了数据中有意或无意的偏差的影响。如果我们不理解程序，我们如何发现这些数据中的偏差？

3. 安全：如果使用机器学习来监管安全系统，我们将不知道哪些漏洞仍然存在，特别是当我们的敌手是不断变化的时候。但如果我们理解代码，我们就可以发现并修补安全漏洞。当然，如果敌手获得了代码，他们也可以发现漏洞。

因果关系

机器学习的局限性

^[19]

^[12]

密码学

^[24]

^[34]

如摩擦力般的复杂性

^[30]

量子计算机的能力

^[1]

^[34]

^[18]

^[3]

复杂性的进展

图同构：

^[4]

^[2]

klog n

电路设计：

^[32]

^[36]

^[39]

^[29]

复杂性的反击：

^[13]

^[6]

不可能的可能性

^[16]

^[14]

参考文献

[1] Arute, F., Arya, K., Babbus, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boxio, S., Brandao, F.G.S.L., Buell, D.A., et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 7779 (2019), 505–510. https://doi.org/10.1038/s41586-019-1666-5

本文经作者授权发表于《返朴》，原文译自Fortnow, Lance. "Fifty years of P vs. NP and the possibility of the impossible." Communications of the ACM 65.1 (2021): 76-85. DOI: 10.1145/3460351