难以近似：独一游戏猜想（二）

一个全新的猜想让计算机科学家们激动不已

Erica Klarreich 著

左   芬      译

【译注：原文2011年10月6日刊载于Simons基金会网站，链接见文末。】

无条件成立

在某种意义上，我们刚才描述过的结果都像是纸牌屋：如果有人证否了UGC，它们全都会坍塌（尽管某种弱化的版本可能会幸存）。随着计算机科学家开始向Khot展示这一观察结果，他逐渐下定决心去演示可以利用UGC中的一些思想来证明一些无条件的定理：结论不依赖于UGC最终得以证明的命题，O’ Donnell说。

Khot专注于所谓Goemans-Linial猜想，一个关于度量空间几何的断言。这些空间配备有度量，也就是，任意两个点之间距离的一种定义。尽管我们都熟悉日常的“鸟瞰”距离（数学家称之为L₂度量），还有很多其它的度量存在。例如，还有出租车度量，也被称为L₁度量：它将两点间的距离指定为由南北向和东西向街道组合而成的最短路径的长度。并且对于一个L₂空间的某些子集而言，L₂度量的平方是另一个度量，叫做L²₂度量。

一个基本的几何问题是，如果你在一个度量空间里选取物体，然后通过另一种度量进行观察，它们会发生多少畸变。例如，假设你在曼哈顿选定了两座建筑，如果你不是驾车往返于其间，而是飞来飞去，能节省多少距离？

Goemans-Linial猜想断言，大体来说，L²₂是L₁度量的一个不太畸变的版本。特别地，它声称存在某个普适的畸变常数K，使得如果你在一个L²₂度量空间里选取任意有限个点的集体，总有办法将它们嵌入（或者用通俗语言来说，摆放到）一个L₁空间里，并且让任两个点的距离不会畸变到超过因子K。

计算机科学家多年前就已知晓这一猜想与寻求所谓最疏割问题的好的近似算法有关。这一问题旨在将一个网络的顶点分成两个近乎相同大小的团簇，并使得团簇之间的边尽可能地少。将网络分成自然团簇的算法对于计算机视觉和数据分析等领域中的问题很有帮助，因为它们为寻找大型数据集中的关联对象集体提供了方法。

精确求解最疏割问题是NP-难的，因此计算机科学家最多只能指望好的近似。生成这种算法的一种方案是设法将网络的顶点嵌入一个L₁空间里，使得顶点间平均来说相距很远，但有边相连的顶点则相当靠近。这样就给出了一种几何的方法来‘识别’网络中的自然团簇，而计算机科学家也已证明这一过程会导出最疏割的一个好的近似算法。可惜的是，没人找到一种有效的方法来生成这样的嵌入。

不过，计算机科学家非常擅长于将顶点嵌入到一个L²₂空间里。如果Goemans-Linial猜想得以证明，那么计算机科学家就明白这一嵌入不过是L₁空间中一个类似嵌入的畸变版本。利用这一知识，他们就可以证明，存在一种算法可以近似最疏割到一个常数因子。

在新千年的最初几年里，计算机科学家已经证明了似乎能导向Goemans-Linial猜想潜在证明的多种结果，因此到2005年时人们情绪高涨。 然而，Khot与如今就职于班加罗尔市微软印度研究院的Nisheeth Vishnoi一同证明，如果UGC成立，那么最疏割无法近似到任何常数因子。这也意味着Goemans-Linial猜想事实上是错的。

既然Goemans-Linial猜想是一个纯粹的几何命题，Khot和Vishhnoi觉得应该可以不借助UGC去证否它，因为UGC毕竟是关于计算复杂性的一个命题。2005年，他们得以证明了这一点，借用了UGC中的想法，但不依赖于UGC这一命题本身。

“他们证明最疏割的这一方案不可行，”O’ Donnell说道，“这有点让人失望，因为它是我们知道的唯一方法，并且人们对它寄予厚望。”

这一发现并非从UGC研究涌现出的唯一无条件结果。这一猜想已经引导研究者们证明了关于投票制度和气泡结构的基本结果（分别见侧边栏：稳定选举与球立方）。

“关于投票和气泡这类事情的一些非常自然的、本身有趣的命题在UGC的研究中忽然凸显出来，”O’ Donnell说道，“哪怕UGC最终不成立，它也激发了大量有趣的数学研究。”

对或错？

尽管UGC中涌现出来的无条件结果已经证实了它对数学与计算机科学界的价值，能知晓它是否成立仍然更好些（说得温和一点）。

在过去五年里，计算复杂性的研究者们在这一问题上耗尽心血，但没有太多的进展，O’ Donnell称。“一半的人努力证明它，另一半的人想要证否它，但他们全都失败了，”他说道，“这表明UGC的成立与否是一个相当困难的问题。”

已经出现的是一堆诱人的半成品结果。比如说，一个发现大致是说如果UGC确实成立，需要超级庞大数目的颜色来使得独一游戏网络的着色难以近似，比涉及PCP定理的相应问题的规模大得多。研究者们还证实，与许多其它问题不同，随机选定的网络并不难于近似，因此无法给出证明UGC的途径。

就在去年，Arora与微软新英格兰研究院的Boaz Barak和David Steurer一同证明，存在独一游戏的次指数算法——也就是说，它比指数算法要快，但还没快到多项式的程度。这意味着独一游戏加入了一个小而独特的问题团簇，它们拥有的最佳已知算法介于指数与多项式之间。“这有点意外，”Arora说。

关于UGC的各种发现让人回想起一则寓言，说的是一群盲人摸到了大象的不同部位，因而每个人都得到了大象实质的不同印象，MIT的Dana Mooshkovitz说道。

“我们知晓了关于UGC的所有这些古怪事情，”她说，“但或许会出现一个证明，将所有这些古怪一扫而空。”

如果某天有人真的揭晓了UGC的内在本质，想出了一个证明，会是值得庆祝的，因为那将意味着（别的先不说了）约束满足问题彻底弄清了。“它很可能会为这一理论画上句号，”O’ Donnell说。

对于诸如黎曼猜想和P与NP问题之类的一些其它著名猜想而言，大多数数学家对预期答案是有共识的。但UGC则截然不同，拥护者和反对者形成了近乎势均力敌的两个阵营，O’ Donnell说。“在很长一段时间内这或许都会是一个开放问题，”他说。

nnn

附录：

侧边栏：有效解

如果你曾经跨国旅行过，就会知道，将大量种类的物品塞进汽车后备箱需要多次尝试，花费很长时间，以及一点巧妙的灵感。相反，如果某人好心帮你装好车了，检查他是否不小心把什么东西落在路边了花不了几秒钟。

P与NP猜想关注的正是可以有效求解的问题与装车这类难于求解但检验已知解是否正确则较为容易的问题之间的差异。

有效性是一个直观上清楚的概念，但对于一个计算问题来说存在一个有效解的确切含义是什么呢？它并不意味着这一问题的每个实例都可以在合理的时间段内求解。对于大多数计算问题而言，得到答案要花费的时长随着‘输入’——我们想要求和的某些数字的长度，或者是我们想要装进行李箱的物品数目——的规模增长而增大。哪怕是两个数字求和这样简单的一个问题，当数字足够长时，求和可能需要花费一年多，一百万年，甚至你想要指定的任何时长。

不过在实践中，我们并不需要对那么长的数字求和。从实用出发，算法并不需要快速求解问题的每一个实例——只需要求解那些输入规模适中（这会随问题不同而有所变化）的实例就够了。只要输入规模增长时算法的运行时间不要增加得过快，它就可以处理我们实际上想要解决的实用案例了。可是多快是过快呢？

1960年代，计算机科学家认定不至过快增长的最合理定义是所谓多项式时间。一个算法说是在多项式时间里运行，如果存在常数C和k，算法至多需要Cn^k步就可以解决输入规模为n的任何问题实例。

不难证明这一概念独立于我们使用的计算模型：如果一个问题在一种类型的计算机上有多项式算法，这一算法可以翻译成任何其它类型计算机上的多项式算法。计算机科学家将这类可以用多项式时间算法求解的问题命名为P类。

多项式函数增长得相对较慢——比诸如2ⁿ这样的指数函数慢得太多了，而后者通常表现为比如说暴力搜索算法的运行时间。运行时间像指数函数一样增长的算法是如此之慢，除非输入规模非常之小，否则根本不实用。而尽管运行时间由n¹⁰⁰这样很大的多项式限定的算法可能也不那么实用，这类算法并不常出现，其原因在于：对于已知在P中的大多数问题而言，计算机科学家都已经找到了运行时间由n³或n⁴这样幂次较小的多项式限定的算法。因此，大多数计算机科学家认同，属于P类的问题就等价于易于求解。

加和两个数字的问题属于P，因为小学学的标准算法是有效的（尽管一个7岁小孩在算的时候可能并非如此）：它的运行时间正比于两个数字的长度。与此相反，计算机科学家至今仍未能找到一个多项式时间的算法来解决装车问题。因此，这一问题可能不属于P类；不过，我们其实已经说到过了，它确实属于另一类，计算机科学家所谓的NP类：存在多项式时间算法来验证给定解是否确实成立的问题类。

P中的任何问题自动地在NP中，但反过来会怎样呢？在1970年代早期，如今在多伦多大学的Stephen Cook和如今在波士顿大学的Leonid Levin各自独立地表述了著名的P与NP猜想：这两个类别是不同的。换句话说，NP中存在问题无法用任何计算机算法在多项式时间内求解，不管它们多么巧妙。

在某种意义上，这一猜想断言创造性无法自动化——在求解问题的能力和仅仅领会他人的解的能力之间存在着本质上的鸿沟。如果这一猜想不对，对这一结果的证明将对大量学科产生深远的影响。

举例来说，在数学中，很容易开发出一个有效算法来检验任何给出的数学证明的正确性。一旦P=NP得到证明，数学家就能将这一算法加以转化，提出对任何真数学命题的有效证明。如果这得以实现，数学领域将从当前形式转变成完全不可思议的样子。

对于许多数学家来说，数学思想可以如此自动化是不可思议的，因此大多数数学家和理论计算机科学家认为P不等于NP。然而在过去40年里所有证明或证否它的尝试之下，这一猜想依然毫不屈服。

——————————————

侧边栏：球立方

有时候，哪怕证明UGC的尝试失败了，仍能有所产出。当O’Donnell， Kindler和魏茨曼研究所的Uriel Feige试图用一种所谓并行重复的技术来处理UGC时，他们发现想要证明的命题规约为关于气泡结构的一个简洁而优雅的问题。

关于气泡的最基本问题已经研究了超过200年了。它说的是，对于每个维度d，用一种几何形状将d-维空间分割成体积1的气泡，那么这种形状拥有的表面积最小是多少。这一问题的2维情形由匹兹堡大学的Thomas Hales于1999年解决——最佳形状就是正六边形，但证明这一结果并不简单。在3维时，一种候选形状已经被认定，但研究者们还未能给出证明。在高维中，我们所知更少。

研究者们证明UGC的尝试归结为与基本气泡难题紧密相关的一个问题，所谓整晶格气泡问题：容许的气泡形状在沿坐标轴平移整数步放置其副本时，必须能铺满空间。在此限制下，哪种形状具有最小的表面积？

举例来说，在2维中，正面形会是一个可行的候选者，因为将它上下左右平移可以铺满平面。而正六边形就不能成为候选者，因为用正六边形填满空间需要在对角线方向做一些平移，并且在水平方向上做一些非整数平移。然而，结果表明最佳整晶格平铺实际上仍是六边形，但不是正的：1989年，首尔市韩国高等研究院的Jaiyoung Choe证明，最佳形状是一种不规则六边形，其周长约为3.86，比正方形的周长4稍稍胜出。

一个d-维立方体有2d个面，所以体积为1的立方体的表面积等于2d。因此，解决d维中整晶格难题的形状的表面积最多为2d（不然的话立方体会将它击败）。此外，由于所有体积1的形状中表面积最小的是球，这一难题的答案的表面积必然大于球的表面积，而球的面积在大的维数下大体上正比于d的平方根。

研究者们预期——并且就证明UGC而言需要——整晶格难题的解的表面积大体上正比于立方体的表面积（也就是2d），在d很大时。然而出人意料地，O’Donnell和Kindler——与Wigderson及目前在西雅图市华盛顿大学的Anup Rao一道——发现对于大的维度d，存在整数步铺满空间的形状，其表面积大体上正比于d的平方根——也就是说，它们的表面积表现得更像是球，而不是立方体。

“存在近乎球的形状，仍然能以立方体的模式铺满空间，这相当反直觉，”O’Donnell说道。UGC能将研究者们引导到关于气泡的这样一个本身有趣的天然问题这件事“增加了它的神秘，”他说。

——————————

侧边栏：稳定选举

在日常选举中，有一定几率有些选票会被误计。误计的选票有多大可能会改变结果，而这一可能性又如何依赖于所采用的投票制度？这 一问题不仅仅是理论上的：事实上，在2000年总统选举中，最终结果取决于佛罗里达州的少量选票是否被正确计数。如果国家法律规定的是多数票制，而不是选举团制度，结果就会毫无争议：所有人都认可在选民投票中，Al Gore胜出五十万张选票以上。

在选票误计下最稳定的投票方法——也就是说，如果少量选票误计了，最不可能改变结果——是相当不道德的那些。始终选择选民A选定的候选者，或者始终让候选者1胜出，这样的制度几乎乃至永远不会被一张误计的选票影响。当然大概没人会在民主选举中选择这样一种制度，因此合理的问题是，在给予所有选民大体上同等权重并且不偏重或轻视任何特定候选者的前提下，哪种投票制度是最稳定的？

在只有两个候选者的情况下，这一难题事实上与最疏割问题有关。想象一个网络，每个顶点代表着所有选民的候选者选择的一种可能组合（因此如果有n个选民，这一网络会有2ⁿ个顶点）。如果在你的选举设定下，通常会有1%的选票被误计，那么如果两个顶点除了大约1%的选民以外是全同的，就把它们用一条边连起来。

一种投票制度不过是为网络中每个顶点指派一个赢家的一种规则。因此，它将网络分成两个子集：候选者1胜出的那些顶点，以及候选者2胜出的那些顶点。这两个集合的规模大体上是相当的，假如我们去除上述讨论的那些具有不公平倾向的投票制度。

为了让投票制度在误计选票的情况下是稳定的，它必须对每条边的两个端点指派相同的结果——换句话说，它不应该把有边相连的顶点放入不同的子集。因此，寻找最稳定的投票制度就对应于寻找网络的最疏割。

事实上Khot，O’Donnell，Kindler和Mossel是2004年在分析最大割的过程中被引导到对投票制度稳定性的分析上的。（尽管最大割和最疏割看起来像相反的问题，它们使用了大量相同的想法和技术，O’Donnell指出。）

研究者们发现，当他们把最大割置于UGC的框架下时，最大割最佳近似为87%这一命题归结为证明投票制度的一个简单命题：即，如果不把两种极端不平衡的投票制度考虑在内，那么多数票制是最稳定的。第二年，O’Donnell，Mossel和华沙大学的Krzysztof Oleszkiewicz得以证明这一“多数制最稳定”定理，印证了2000年总统选举中的直觉。

“其他人之前也思考过投票稳定性，但UGC真正让我们聚焦于这一确切命题，并给予了我们很强的动机去证明它，”O’Donnell说道。

nnn

原文链接：

https://www.simonsfoundation.org/2011/10/06/approximately-hard-the-unique-games-conjecture/

转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。

链接地址：https://wap.sciencenet.cn/blog-863936-1473180.html?mobile=1

收藏

分享