计算机科学年

困难的问题，困难的答案

50 年来，计算机科学家一直试图解决其领域中最大的悬而未决的问题，即“P 与 NP”。它粗略地询问某些难题的难度。 50年来，他们的尝试都以失败告终。很多时候，当他们开始用新方法取得进展时，他们遇到了障碍，证明这种策略永远不会奏效。最终，他们开始想知道为什么证明某些问题如此困难。他们为回答此类内向问题所做的努力已经发展成为一个称为元复杂性的子领域，它为这个问题提供了迄今为止最深刻的见解。

在八月份的一篇文章和一个简短的纪录片视频中，广达准确地解释了我们所知道的、我们如何知道它以及我们刚刚开始弄清楚元复杂性的内容。关键的不仅仅是所涉及的研究人员的好奇心：解决 P 与 NP 的问题可以解决无数的逻辑问题，使所有密码学变得毫无意义，甚至可以揭示已知和永远超出我们掌握的事物的最终本质。

大型语言模型的力量

把足够多的东西放在一起，你可能会对发生的事情感到惊讶。水分子产生波浪，成群的鸟儿一体地俯冲和翱翔，无意识的原子组合成生命。科学家将这些称为“涌现行为”，他们最近发现大型语言模型也发生了同样的事情——人工智能程序经过大量文本集合的训练，以产生类似人类的书写。当它们达到一定的规模后，这些模型突然可以做一些较小模型做不到的意想不到的事情，例如解决某些数学问题。

然而，人们对大型语言模型的兴趣激增引发了新的担忧。这些程序制造谎言， 造成社会偏见，甚至无法处理人类语言的一些最基本的元素。此外，这些程序仍然是一个黑匣子，其内部逻辑不可知，尽管一些研究人员对如何改变这一点有想法。

解决消极情绪

计算机科学家早就知道可以快速浏览图形（由边缘连接的节点网络）的算法，其中连接有一定的成本，就像连接两个城市的收费公路一样。但几十年来，当道路可能有成本或回报时，他们找不到任何快速算法来确定最短路径。去年年底，三位研究人员提出了一种可行的算法，其速度几乎与理论上一样快。

然后在三月份，研究人员发布了一种新算法，可以精确地确定两种类型的数学对象（称为组）何时相同；这项工作可能会导致算法能够更广泛地快速比较组（也许还有其他对象），这是一项非常困难的任务。今年的其他重大算法新闻包括通过结合随机和确定性方法来计算素数的新方法， 驳斥了关于信息有限算法性能的长期猜想，以及显示非直观想法如何改进算法的分析。梯度下降算法的性能，该算法在机器学习程序和其他领域中无处不在。

欣赏AI艺术

像 DALL·E 2 这样的图像生成工具今年急剧流​​行。只需向他们提供书面提示，他们就会吐出一幅艺术画面，描绘您所要求的任何内容。但使大多数人造艺术家成为可能的工作已经酝酿了很多年。基于描述流体扩散的物理学概念，这些所谓的扩散模型有效地学习如何将无形的噪声解读为清晰的图像——就好像把一杯咖啡的时钟倒转，看到均匀分布的奶油重新构成一个良好的状态。定义的团块。

人工智能工具在提高现有图像的保真度方面也取得了成功，尽管我们距离警察反复喊“增强！”的电视比喻还很远。最近，研究人员转向扩散以外的物理过程来探索机器生成图像的新方法。一种由泊松方程控制的新方法描述了电力如何随距离变化，已经证明在某些情况下比扩散模型更有能力处理错误并且更容易训练。

提高量子标准

几十年来，肖尔的算法一直是量子计算机能力的典范。这套指令由 Peter Shor 于 1994 年开发，允许机器利用量子物理学的怪癖，将大数分解为质因数，速度比普通的经典计算机快得多，这可能会浪费大部分互联网的安全系统。八月，一位计算机科学家开发了 Shor 算法的更快变体，这是自其发明以来的第一个重大改进。 “我本以为任何适用于这个基本轮廓的算法都注定会失败，”肖尔说。 “但是我错了。”

然而实用的量子计算机仍然遥不可及。在现实生活中，微小的错误可能会迅速累积起来，破坏计算并剥夺任何量子优势。事实上，去年年底，一组计算机科学家表明，对于特定问题，经典算法的表现与包含错误的量子算法大致相同。但希望还是有的：8 月份的工作表明，某些纠错码（称为低密度奇偶校验码） 的效率至少比当前标准高 10 倍。

人工智能中隐藏秘密

在密码学和人工智能交叉领域的一个不寻常的发现中，一组计算机科学家表明，可以在机器学习模型中插入某些几乎不可见的后门，它们的不可检测性由与最好的现代加密方法相同的逻辑支持。研究人员专注于相对简单的模型，因此尚不清楚当今大部分人工智能技术背后的更复杂模型是否也同样如此。但这些发现确实为未来的系统提供了防范此类安全漏洞的方法，同时也表明人们对这两个领域如何帮助彼此发展重新产生了兴趣。

此类安全问题是Cynthia Rudin倡导使用可解释模型来更好地理解机器学习算法内部发生的情况的部分原因；与此同时，即使面对迫在眉睫的量子技术， Yael Tauman Kalai等研究人员也推进了我们的安全和隐私概念。隐写术相关领域的一项成果 展示了如何在机器生成的媒体中以完美的安全性隐藏消息。

矢量驱动的人工智能

尽管人工智能已经变得如此强大，但支撑大多数现代系统的人工神经网络却有两个缺陷：它们需要大量资源来训练和操作，而且它们很容易成为难以理解的黑匣子。许多研究人员认为也许是时候采取另一种方法了。人工智能系统可以用无限变化的超维向量（数千个数字的数组）来表示概念，而不是使用人工神经元来检测个体特征或特征。该系统更加通用，能够更好地处理错误，使其计算更加高效，并且它允许研究人员直接处理这些模型所考虑的想法和关系，使他们能够更深入地了解模型的推理。超维计算仍处于起步阶段，但随着它接受更大的测试，我们可能会看到新方法开始占据主导地位。