编译者按：该文有些烧脑，“假设你知道区分你能解决的问题和你几乎能解决的问题的难度是NP”，如果可以忍受上面这句话，请继续
是否有可能用像球体一样的形状以“立方体”方式填充空间？几何和理论计算机科学的交叉研究证明这是可以的。
在四世纪，希腊数学家，亚历山大的帕普斯赞扬了蜜蜂的“在几何学方面深思熟虑”。它们蜂窝的六边形结构似乎是将二维空间划分为相同面积和最小周长单元的最佳方式——允许昆虫减少它们需要生产的蜡，并花更少的时间和精力建造蜂巢。
或者帕普斯和其他人是这样假设的。几千年来，没有人能证明六边形是最佳的——直到1999年，数学家托马斯·黑尔斯终于表明，没有其他形状可以做得更好。今天，数学家仍然不知道哪些形状可以以尽可能小的表面积铺覆(tilt)在三个或更多维度上。
这种“泡沫”问题有广泛的应用——对于研究肥皂泡（或泡沫）行为的物理学家和分析晶体结构的化学家来说，对于探索球体填充排列的数学家和开发有效数据处理技术的统计学家来说，都有用。
在2000年代中期，泡沫问题的特殊表述也引起了理论计算机科学家的注意，他们惊讶地发现，这个问题与他们领域的一个重要的开放问题密切相关。他们能够利用这种连接找到一种最小表面积的新高维形状。
“我喜欢来来回回研究这个，”普林斯顿大学的Assaf Naor说。“一些古老的数学与计算机科学相关；计算机科学提供回报并解决了数学问题。当这种情况发生时，这非常好。”
但这种形状虽然是最佳的，但缺少了一些重要的东西：几何基础。由于它的存在已经用计算机科学的技术得到证明，因此它的实际几何形状很难掌握。这就是Naor和纽约大学Courant研究所的计算机科学家Oded Regev上个月在网上发表的证明中着手纠正的问题。
Regev说：“这是故事的一个非常好的结局。”
立方泡沫
数学家考虑了泡沫问题的其他版本——包括如果您只被允许根据所谓的整数晶格划分空间会发生什么。在该版本的问题中，您取一个均匀间隔点的正方形数组（每个相距1个单元），并将每个点都作为形状的中心。“立方体”泡沫问题就是，当您被要求以这种方式覆盖空间时，最小表面积是多少。
研究人员最初有兴趣施加这种限制，以了解称为流形的拓扑空间的性质。但这个问题有了自己的一套，在数据分析和其他应用中变得相关。
它在几何上也很有趣，因为它改变了“最佳”可能意味着什么。例如，在二维中，如果正六边形只能在水平和垂直方向上按整数移动，则它们就不能再铺覆平面。（你必须将它们按无理数量，irrational amounts，在两个方向中的一个方向上移动。）
正方形可以。但这是能做的最好的吗？正如数学家Jaigyoung Choe在1989年发现的那样，答案是否定的。相反，最佳形状是向一个方向压扁并向另一个方向拉长的六边形。（当六边形的面积为1时，其周长约为3.86——正方形周长为4）
这些差异可能看起来微不足道，但在更高的维度中，差异会变得更大。
在给定体积的所有形状中，最小化表面积的形状是球体。随着n维数的增加，球体的表面积与n的平方根成正比增加。
但球体不能在不留下缝隙的情况下铺覆空间。另一方面，体积为1的n维立方体（n-dimensional cube of volume 1）可以。思路是它的表面积为2n，与其维度成正比。体积为1的10,000维立方体的表面积为20,000——比400大得多，大约是10,000维球体的大致表面积。
因此，研究人员想知道他们是否可以找到一个“球形立方体”——一种像立方体一样铺覆n维空间的形状，但其表面积像球体一样缓慢生长。
这似乎不太可能。卡内基梅隆大学理论计算机科学家Ryan O’Donnell说：“如果你想让你的气泡准确地填满空间，并以这个立方网格为中心，除了立方体气泡，很难想象你会用什么。”“看起来立方体真的应该是最好的。”
我们现在知道它不是。
难题的难度
几十年来，立方泡沫问题在更高维度上相对没有被探寻过。第一批在这方面取得进展的研究人员不是来自几何领域，而是来自理论计算机科学。他们在寻找一种方法来证明他们领域被称为独特游戏猜想（unique games conjecture，UGC）的核心陈述时偶然遇到了它。Regev说：“独特游戏猜想是我目前认为的理论计算机科学中最大的开放式问题。”
该猜想由当时的研究生Subhash Khot于2002年提出，假设如果一个特定问题——涉及为网络节点分配颜色的问题——无法完全解决，那么即使找到一个近似解决方案也非常困难。如果属实，该猜想将使研究人员能够一举了解各种其他计算任务的复杂性。
数学家认为，一种称为Weaire-Phelan结构的形状是表面积最小的3D空间。虽然他们尚未证明这一点，但物理实验为这一假设提供了额外的支持。爱尔兰都柏林三一学院的研究人员用肥皂泡填充了一个特殊的模具，发现他们自然而然地将自己安排成Weaire-Phelan模式。
计算机科学家通常根据是否可以使用高效的算法来对任务进行分类，或者它们是否是“NP难度的”的问题（这意味着只要关于计算复杂性的广泛相信但未经证实的猜测是真的，就无法随着问题的规模的增长而有效解决的问题）。例如，旅行销售人员问题要求只访问一次网络中的每个城市所需的最短路径，这是NP难的。确定一个图——由边缘连接的顶点集合——是否可以用最多三种颜色标记，以便任何两个连接的顶点具有不同的颜色。
事实证明，NP难度意味着很难为其中许多任务找到大致的解决方案。假设您想以满足一些约束列表的方式标记不同颜色的图形的顶点。如果满足所有这些限制是NP难度，那么如果只满足90%，即75%或50%呢？在某个阈值以下，也许可以想出一个有效的算法，但超过这个阈值，问题就变得N P难度了。
几十年来，计算机科学家一直致力于确定不同感兴趣的优化问题的门槛。但有些问题回避了这种描述。虽然算法可以保证80%的最佳解决方案，但实现95%的最佳解决方案可能很难，而问题正好在80%到95%之间进入NP难度的范围。
独特游戏猜想，或UGC，提供了一种立即确定答案的方法。它提出了一个声明，起初似乎更有限：区分几乎可以满足所有特定着色约束（例如，超过99%）的图形和几乎不能满足任何着色约束的图形（例如，不到1%）之间的区别，这是一个NP难度问题。
但在2002年提出UGC后不久，研究人员表明，如果猜想是真的，那么您可以轻松计算任何约束满意度问题的难度阈值。（这是因为UGC还意味着已知算法可以实现所有这些问题的最佳近似值。）“这正是所有这些优化问题的关键，”Ryan O’Donnell说。
因此，理论计算机科学家开始证明UGC——这项任务最终导致他们中的一些人发现了球形立方体。
让难题更难
2005年，O’Donnell说在微软研究公司工作。他和两名同事——现任魏茨曼理工学院的Uriel Feige和耶路撒冷希伯来大学的Guy Kindler——联手应对UGC问题。
他们对如何继续这个研究有一个模糊的想法。他们将从一个关于图的问题开始——这个问题与UGC非常相似。所谓的最大切割（“最大切割”）问题在给定图时询问如何将其顶点划分为两个集合（或颜色），以便连接这些集合的边的数量尽可能大。（您可以将最大切割视为一个关于用两种颜色为图形着色的最佳方法的问题，以便尽可能少的边缘连接相同颜色的顶点。）
如果UGC为真，这意味着，给定一些随机图，有效的近似算法只能达到该图真实最大切口的87%左右。做得更好是NP难度。
Feige、Kindler和O’Donnell反而行之：他们希望证明最大削减很难近似，然后用它来证明UGC。他们的计划依赖于一种称为并行重复或者平行重复（parallel repetition) 的技术——一种使难题更难的聪明策略。
假设你知道区分你能解决的问题和你几乎能解决的问题的难度是NP。并行重复使您能够在此基础上显示更强的难度结果：区分可以解决的问题和几乎无法解决的问题的难度也是NP。Naor说：“这种非直觉、深刻的现象......在当今许多计算机科学的核心问题中。”
但有一个陷阱。并行重复并不总是像计算机科学家希望的那样放大问题的难度。Regev说，特别是最大切割问题的几个方面“给并行重复造成了很大的麻烦”。
Feige、Kindler和O’Donnell专注于表明，尽管有麻烦，但平行重复还是可以起作用。德克萨斯大学奥斯汀分校的理论计算机科学家Dana Moshkovitz说：“分析起来真的很复杂。”“但这似乎很接近。并行重复似乎[帮助]从最大削减到独特游戏的这种联系。”
作为热身，研究人员试图理解一个简单的最大切割案例的并行重复，莫什科维茨称之为“最愚蠢的最大切割”。考虑由边缘连接的奇数顶点来形成一个圆，或“奇数循环”。您想用两种颜色之一标记每个顶点，这样就没有一对相邻的顶点具有相同的颜色。在这种情况下，这是不可能的：一条边总是连接相同颜色的顶点。您必须删除该边，“打破”奇数循环，才能让您的图满足问题的约束。最终，您希望最小化需要删除的边的数量，以便正确给图上色。
并行重复允许您考虑这个问题的高维版本——在这个版本中，您必须打破出现的所有奇数循环。Feige、Kinderler和O’Donnell需要证明，随着尺寸数量变得非常大，您必须删除非常大的边缘才能打破所有奇数循环。如果这是真的，这意味着并行重复可以有效地放大这个“愚蠢的最大切割”问题的难度。
就在那时，团队发现了一个奇怪的巧合：有一种几何方法来解释并行重复是否会像他们希望的那样工作。秘密在于立方泡沫的表面积。
从柠檬到柠檬水
他们的问题用泡沫的语言重写，归结为表明球形立方体不可能存在——不可能沿着整数晶格将高维空间划分为表面积比立方体小得多的单元格。（正如计算机科学家希望的那样，更大的表面积相当于需要删除奇数周期图中更多“坏”边缘。）
“我们当时想，哦，多么奇怪的几何问题，但这可能是真的，对吧？”O’Donnell说。“我们真的需要这个才能成为真正的答案。”但他、Feige和Kindler无法证明这一点。因此，在2007年，他们发表了一篇论文，概述了他们计划如何利用这个问题来帮助攻击UGC。
很快，他们的希望破灭了。
普林斯顿大学的理论计算机科学家Ran Raz已经证明了平行重复的几个主要结果，他对他们的论文很感兴趣。他决定分析奇周期问题的并行重复，部分原因是Feige、Kinderler和O’Donnell发现了这个问题与几何学的联系。
Raz不是从泡沫问题开始的，而是正面攻击了计算机科学版本的问题。他表明，你可以删除更少的边缘来打破图中的所有奇数循环。换句话说，并行重复不能充分放大这个最大切割问题的难度。Moshkovitz说：“人们从并行重复中获得的参数完全没有给出这一点。”
O’Donnell说：“我们使用并行重复来显示独特游戏的难度的计划在最简单的情况下甚至都行不通。”“这打破了整个计划。”
虽然令人失望，但Raz的结果也暗示了球形立方体的存在：能够铺覆n维空间的形状，其表面积与n的平方根成比例缩放。O’Donnell说：“我们想，好吧，让我们用柠檬制作柠檬水，并利用这个关于平行重复和离散图形的令人失望的技术结果，并将其转化为几何学方面整洁、有趣的结果。”
他和Kindler与计算机科学家Anup Rao和Avi Wigderson合作，仔细研究了Raz的证明，直到他们很好地学习了其技术，将它们转化为泡沫问题。2008年，他们表明球形立方体确实是可能的。
普林斯顿大学的马克·布拉弗曼说：“这是对这个问题进行推理的好方法。”“太美了。”
它在故事的几何方面提出了问题。因为他们利用Raz在平行重复方面的工作来构建他们的铺覆形状，Kindler、O’Donnell、Rao和Wigderson最终得到了一些丑陋和类似于Frankenstein的东西。铺覆体乱七八糟，充满了凹痕。用数学术语来说，它不是凸的。虽然这符合他们的目的，但球形立方体缺乏数学家喜欢的属性——这些属性使形状更具体，更容易定义和研究，并且更适合潜在的应用。
Regev说：“他们的构建有一些非常不令人满意的地方。”“它看起来像变形虫。它看起来不像你所期望的，一个漂亮的铺覆体。”
这就是他和Naor开始寻找的。
挣脱笼子
从一开始，Naor和Regev就意识到他们必须从头开始。麻省理工学院的理论计算机科学家 Dor Minzer说：“部分原因是凸体限制性如此强，以前的技术都没有机会工作。”
事实上，凸性限制性太强是完全合理的——凸球形立方体根本不存在。
但上个月，Naor和Regev证明，你可以沿着整数坐标用凸形划分n维空间，其表面积非常接近球体的表面积。他们完全以几何方式做到了这一点——将问题恢复到数学根源。
他们首先必须绕过一个主要障碍。立方泡沫问题要求每个铺覆体都以整数坐标为中心。但在整数晶格中，一些点之间的距离非常短——这些短距离会带来麻烦。
考虑二维网格中的一个点。它距离水平和垂直方向最近的点有1个单位。但在对角线方向，最近的点是根号2个单位外——这种差异在更大的空间中会变得更糟。在n维整数格中，最近的点仍然在1个单位之外，但那些“对角线”点现在根号n个单位以外。例如，在10,000维中，这意味着离任何点最近的“对角线”邻居距离100个单位，即使还有10,000个其他点（每个方向一个）距离只有1个单位。
在其他晶格中，这两种距离成比例地增长。几十年来，数学家们就知道如何用最小表面积的凸形铺覆体铺这些格子。
但在整数格中，最短的距离总是卡在1。这阻碍了构建最佳表面积的漂亮铺覆体。“他们把你关在这个笼子里，”Regev说。“他们让你周围的一切都变得非常紧张。”
因此，Naor和Regev反而考虑了全n维空间的一部分。他们仔细选择了这个子空间，这样它仍然富含整数点，但这些点都不会太接近。
换句话说，他们最终得到的子空间正是数学家已经知道如何优化铺覆的类型。
但这只是工作的一半。Naor和Regev需要划分整个空间，而不仅仅是其中的一部分。要获得n维球形立方体，他们必须用剩余空间的铺覆体乘以其有效铺覆体（就像如何用一维线段乘以二维正方形以获得三维立方体）。这样做会将他们的建筑提升回原始空间，但它也会增加其表面积。
这两个学者必须证明剩余空间的不是最有的铺覆体，没有给表面积增加太多。一旦他们这样做到了，他们的构建就完成了。（它们的最终形状的表面积比非凸球形立方体大一点，但他们认为可能可以找到与非凸形对应物一样高效的凸面铺覆体。）
数学家Noga Alon说，“他们的证明与之前关于球形立方体的工作完全不同”。“回想起来，这可能是一个更自然的证据。这是某人一开始就应该尝试的。”
“当事情以不同的方式做时，”Raz补充说，“有时你会发现有趣的额外含义。”
希望重新点燃
目前还不清楚这些研究隐含的意义可能是什么——尽管这项工作利用了整数格在密码学和其他应用中的潜在用途。Alon说，鉴于这个问题与其他领域之间的联系，“它可能会导致其他事情。”
目前，计算机科学家看不到以平行重复和UGC来解释凸结果的方法。但他们没有完全放弃使用泡沫问题来证明这个猜测的原始计划。Kindler说：“您可以通过各种方式试图颠覆我们遇到的明显障碍。”
Braverman和Minzer在2020年重新审视泡沫时尝试了一种方式。他们没有要求铺覆体形状是凸的，而是要求它遵守某些对称性，这样无论你如何翻转坐标，它看起来都是一样的。（在二维中，正方形可以工作，但矩形不会起作用；迄今为止描述的高维球形立方体也不会起作用。）在这种新的约束下，这对学者能够展示Kindler和其他人15年前所希望的：毕竟，你不可能比立方体的表面积做得更好。
这相当于一种不同的平行重复——这将使最简单的最大切割情况尽可能困难。虽然结果为这一研究提供了一些希望，但目前还不清楚这个版本的并行重复是否适用于所有最大切割问题。Braverman说：“这并不意味着你完成了。”“这只是意味着你又回来继续这个事情。”
Minzer说：“几何学有很大的潜力。”“只是我们不太了解它。”
编译：htb，信息来源自quantamagazine.org，作者Jorhana Cepelewicz，略有修改
