面对NP问题时，人们通常可以将NP问题表述为可满足性或混合整数规划问题，并将其扔给目前最好的求解器来借助计算机的力量，自动找到答案。这些工具已经成功用于电路和代码的验证、自动化测试、计算生物学、系统安全、产品和包装设计、金融交易，甚至是一些困难的数学问题求解之中了。人们通常无法忽视机器学习在近些年带来的革命性影响，尤其是神经网络。人工神经网络建模的概念基础，基本上是计算加权阈值函数。这种思想起源于1940年代Warren Mcculloch和Walter Pitts的工作。在1990年代，Yoshua Bengio、Geoffrey Hinton和Yann Lecun开发了反向传播算法，来将深度神经网络的层数加深，并得到非凡的结果。与此同时计算机硬件计算、存储等方面出现突破，那些更快、更加分布式的计算单元，那些专用的硬件和海量的数据有助于推动机器学习完成很多类似人类的功能。ACM认识到Bengio 、Hinton和LeCun的贡献，并在2018年为他们颁发了图灵奖。有的同学可能会问，机器学习怎么和P、NP问题相联系呢？奥卡姆剃刀说：如无必要，勿增实体。如果P=NP，我们可以用这个思想来创造强大的学习算法：找到与数据一致的最小电路。即便P≠NP，机器学习也可以学习并且近似这种思想，这就赋予它强大的能力。尽管如此，神经网络也可能不是真正的“最小”的电路，当然或许可能是尽量小的。今天我们所使用的深度学习方法通常是结构固定的，能够变动的都是神经元连接上的权重。为了能够实现足够泛化的表达能力，这些网络通常有几百上千的权重数量。这就限制了深度网络的能力（也就是不够简单）。它们可以在人脸识别上做的很好，但是无法根据示例学习乘法。让我们考虑二进制字符串的无限集上的分布场景。我们虽然不能拥有均匀分布，但是可以创建一种每个长度相同的字符串都有相同概率的分布。但是，有些字符比其他字符更重要。比如π的前一百万位数字比随机生成的一百万位数字更有意义。我们可能希望将更高的概率放在更有意义的字符上。现在我们有很多方法能够做到这点。实际上，已经有人发现了一种接近任何其他可计算分布的通用分布，这种分布与学习有很大的联系——例如，任何能够以小错误率学习这个分布的算法，将可以学习所有的可计算分布。但是问题在于，即使P=NP，这种分布通常也是不可计算的。如果P=NP，我们仍然可以通过创建一个对其他有效可计算分布通用的分布来获取一些有用的信息。那么我们能够从机器学习中得到什么？让我们考虑生成式预训练Transformer（GPT）。在2020年5月GPT-3发布了，它有1750亿个参数，并且训练了4100亿个token。这些Token来自很多的文字语料库。它能够回答问题，能够根据提示写出文字，甚至可以进行一些基础的编码工作。尽管还有很长的路要走，但是GPT-3因其生成内容的自然性而受到广泛的赞誉。在某种意义上，我们可以将GPT-3视作一种特殊的分布方法。我们可以在其中查看算法生成输出的概率，这是通用分布的一种弱化版本。如果我们将通用分布限制为具有给定前缀，则会提供由该前缀提示的随机样本。GPT-3也可以建立在此类提示的基础上，无需进一步训练即可处理范围广泛的领域知识。随着这一系列研究的发布，我们将更接近一个可以执行内置学习的通用衡量标准：从给定的上下文中学习一个随机样例。
