精选
难以近似：独一游戏猜想（一）
一个全新的猜想让计算机科学家们激动不已
Erica Klarreich 著
左 芬 译
【译注：原文2011年10月6日刊载于Simons基金会网站，链接见文末。】
尽管伟大的定理称得上数学的终极目标，伟大的猜想往往在增进理解和创建新理论方面作用更大。在这一点上体现得最明显的莫过于计算复杂性，也就是对标准计算机可以处理的计算性问题种类的研究。著名的P与NP猜想——提出40年后仍未解决——在设定其领域的基本规则和恰当语言方面可能超过了现代的任何其它单条数学论断。
1971年提出的这一猜想将计算机科学家们的注意力集中于两类问题的对比上：P, 计算机可以有效解决的问题类，以及NP，对于这类问题计算机可以有效检验一个给定解是否正确，哪怕它没能力一开始就找到这个解。天然的计算问题大多落到这两个类别中的一个。这一猜想认为——并且大多数计算机科学家相信——这两种类别是不同的，意味着NP中存在一些问题，它们的求解超出了任何有效计算机算法的能力。
现在，计算复杂性领域又被一个全新的猜想点燃了。它尽管不像P与NP猜想那么伟大，却在某种意义上从其止步的地方继续往前。如果这一‘独一游戏猜想（Unique Games Conjecture）’成立，那么对于许多人们很想解决的问题，不仅仅找到精确解很困难——哪怕找到一个好的近似解也超出了计算机的能力。
“这一猜想就像一个锚，我们可以把大量近似问题都连接上去，”普林斯顿高等研究院的Avi Wigderson说道，“它生成了一套理论。”
原始的P与NP猜想提出至今已经四十年，始终难以证明。但在此期间，计算机科学家们积累了大量证据支持它的正确性。他们证明数以千计的实际问题——例如，最佳芯片设计方案，最优飞机航线规划，以及蛋白质的最低能量构型——是NP-难的，意味着针对其中任一个问题的一个有效算法会自动给出NP中所有问题的有效解法（也就意味着P=NP）。至今为止，还没有人成功给出这数千个问题中任一个的有效算法，甚至都没人愿意尝试。如果这一猜想是对的，永远不会有人能做到。
（更多关于有效性以及P与NP猜想的内容见侧边栏，有效解。）
不过，假如你并不指望得到一个完美的芯片设计，能得到一个比较不错的就很满意。在过去的数十年里，计算机科学家已经针对这类问题的一些想出了很好的近似算法，而对于其它一些问题，他们则证明好的近似算法不存在。不过，对于人们热衷于求解的许多问题，它们是否可以近似求解以及能近似到何种程度，计算机科学家们仍茫然不知。
如今，独一游戏猜想（UGC）给予了研究者们一种新的工具来驯服这些棘手的问题。它由如今任职于纽约大学的Subhash Khot于2002年提出，说的不过是给网络节点指派颜色的一个特定问题哪怕近似求解也是NP-难的。
表面看来，这个猜想像是一个相当狭隘的命题（尽管可能难以证明，甚至可能是错的）。然而，在过去的十年里，计算机科学家们发现，出乎他们的意料，如果这一猜想是对的，那么一大群问题——其中有些看起来跟原始的独一游戏问题几乎毫不相干——也同样难以近似。这些发现让研究者们绞尽脑汁想要弄清楚这一特定的网络着色问题究竟有什么神奇之处。
“这一猜想像是一把魔力钥匙，使得大量问题更加简单和清楚，”匹兹堡市卡内基梅隆大学的Ryan O’ Donnell说道，“它改变了我们思考这些问题的方式。”
跟许多伟大的猜想一样，UGC在各种各样看起来跟计算复杂性相距甚远的领域里引发了新发现。这些领域包括膜的结构，以不同方式测量距离得到的几何，甚至不同投票系统的优劣。
同样与许多伟大的猜想一样，UGC具有推动计算复杂性领域本身进步的潜力，不论它最终被证实或证伪。如果被证实，它会为多种近似问题给出精确的困难性结果，并且在一大类被称为约束满足问题的情形下，它会表明解决这些问题的‘显然候选’方法其实是最优的，从而为这一研究领域画上圆满的句号。证伪UGC可能更加激动人心，因为这需要开发出一种全新的强力近似算法，而它可能跟目前已知的近似算法有显著的差别。
“我确信，不管它最终成立与否，这一猜想的光芒都不会怎么暗淡下去，”亚特兰大市佐治亚理工学院的Richard Lipton在一篇关于UGC的博客中写道，“需要最高水平的见地、创造性以及一点‘胆量’才能提出这样一个猜想。”
精确的困难性
要对UGC有望阐明的这类近似问题有所感知，我们把注意力集中到一个被称为最小顶点覆盖的古典问题上。这一问题可以用到通信，土木工程，电子工程以及生物信息学中。对于给定的网络——一些节点（也称为顶点）和连接一些顶点的边的集体——顶点覆盖是顶点的一个子集（称为覆盖），使得网络中的每条边都与覆盖中至少一个顶点接触。最小顶点覆盖问题要求找到顶点数目最少的一个覆盖。
找到最小的可行顶点覆盖的一种方法是直接查询所有顶点子集，排除不是顶点覆盖的那些，接着看剩下的子集哪个最小。可是，对于有n个顶点的网络来说，有2n个子集需要检验。像2n这样的指数因子会很快地增长，使得对于相对较小的n值，哪怕用最快的计算机去运行这一算法也需要花费比宇宙年龄还长的时间。
计算机科学家们之间的共识是，一个计算机算法要称得上有效的话，它的运行时间最多只能是输入规模n的多项式函数——也就是说，像2n2+1或4n3+n这种（事实上，这就是算法归属于P类的含义）。1972年，加州大学伯克利分校的Richard Karp惊人地证明了最小顶点覆盖的多项式算法不存在，除非P=NP：换句话说，这一问题是NP-难的。
于是，在证明不了P=NP的情况下，研究者们最多只能指望有一个有效的近似算法：它可以确保给出一个相当小的顶点覆盖，但可能不是最小的。
幸运的是，这样的算法很容易就能找到：先在网络中选择任一条边，把它的两个端点放入你的子集。从网络中删除这两个顶点以及跟它们之一接触的所有边，接着重复这一过程，从新的，更小的网络中选出一条边，并将它的两个端点放入你的子集。一直持续这一过程直到所有边都被删除。这最多需要n/2步，所以它是有效的，不像前面那种算法。得到的子集会是一个顶点覆盖，并且尽管它可能不是最小的，它最多只会多出一倍的顶点，因为在每一轮中任何顶点覆盖都必须包含选定的两个顶点中至少一个。计算机科学家称这一算法实现了2-因子近似。
既然这一算法如此简单，看起来很有可能一个更巧妙的算法能做得更好，更接近最少所需要的顶点数。确实，在P与NP猜想提出后的前二十年里，许多计算机科学家认为获得一个NP-难问题的好的近似一定比找到精确解容易些，普林斯顿大学的Sanjeev Arora称。“人们的直觉就是你可以用多种多样的方法来处理一个问题，总能得到近似解。”
但一直没有人想出一个算法可以近似最小顶点覆盖到任何小于2的常数因子。诸如此类的经验让计算机科学家们开始琢磨，是否对于有些问题，找到好的近似解跟找到精确解完全是一样难的——也就是说，是NP-难的。
1992年，计算机科学家取得了一次突破：这就是著名的PCP定理，一个非常强力，但也相当技术化的成果，它使研究者得以证明某些问题即使近似到超过某个因子也是NP-难的。例如，利用PCP定理，以色列雷霍沃特市魏茨曼科学研究所的Irit Dinur与特拉维夫大学的Samuel Safra在2002年证明，假定P不等于NP，则不存在最小顶点覆盖的近似因子小于
，也就是大约1.36的有效算法——也就是，确保总是给出超出最小值至多36%的顶点覆盖的算法。
跟这个类似的结果——已知最佳算法的近似因子与困难性结果的近似因子间存在间隙——给研究者们带来了一个诱人的问题。在最小顶点覆盖的情形下就是，我们描述过的简单算法取得的2-因子近似是否已达最佳，只不过PCP定理还没有强大到足以去证明它？还是确实还存在更好的算法，它可以实现1.36-因子近似？
这类问题不仅仅在理论计算机科学家看来是有趣的。将芯片设计算法从3-因子近似改进到2-因子近似可能意味着通过提高效率可以节省数百万美元，但如果不存在这种改进，最好预先知晓这一点，否则就会陷入徒劳无功的探索。
于是，一旦PCP定理使研究者得以证明近似困难性结果，很自然地计算机科学家们会“贪得无厌”，Wigderson说道。计算机科学家们开始想要精确的困难性结果，也就是，像“可以近似问题X到因子Y，但要做到更好会是NP-难的”这种形式的定理。
在1990年代末期，斯德哥尔摩皇家理工学院的Johan Håstad在一篇里程碑式的文章中阐明了如何针对一些特定问题得到精确的困难性结果。一些研究者设法改造了他的推导以处理更多问题，但对于许多问题而言，要实施这一范式似乎有无法逾越的技术障碍。
“还有大量重要问题我们就是无法着手，”Wigderson说。
而这就是2001年时的现状，直到一个年轻的普林斯顿研究生敲开了他导师的门，并吐露了他一直在琢磨的一种全新的近似困难性想法。
独一游戏猜想
这个学生，Subhash Khot，注意到他一直在研究的一个近似问题的许多困难部分似乎都浓缩在关于网络顶点颜色指派的困难性的一个猜想中了。几天后，他告诉他的导师Sanjeev Arora这一猜想对另一个问题也有帮助。Arora认为这一猜想值得写下来，但可能还没有重要到可以提交到最好的计算机科学会议上去。
“我们没想到它会变得如此关键，”Arora回想道。
Khot的独一游戏猜想植根于网络着色问题：给定一个网络和一组颜色，是否可以对网络中的顶点适当着色，使得任两个共边的顶点总是具有不同的颜色？
在只有两种颜色（比如，红色与绿色）的情况下，对于任何给定网络可以很快地回答这个问题：直接从一个任意的顶点出发，将它着为（比方说）红色。现在所有与这个点相邻的顶点都得着为绿色。给这些点着好色后，继续给每个已着色顶点的所有邻点着色，直到你遇到矛盾或者成功为整个网络着色。
如果你用的超过了两种颜色，那么选定一个顶点的颜色并不会固定与它相邻的任何顶点的颜色，因此无法实施上述这样简单的一个算法。事实上，当超过两种颜色时，判定哪种网络可以着色是一个NP-难的问题。
Khot决定在双色算法和多于双色的困境之间架起一座桥梁。他考虑配备了一套着色规则或者说约束的网络，使得当两个顶点有边相连时，一旦一个顶点被着色，约束会指定另一个顶点的颜色。对于这类网络，跟双色情况类似的一个算法会很轻松地判定给定网络是否能以满足约束的方式着色。
在理论计算机科学家们看来，自然的后续问题就是这一问题的优化版本：对于无法以满足所有约束的方式着色的网络，哪种着色方式能满足尽可能最多的约束？我们称此为独一游戏问题（这一命名源自该问题的一种不同形式，陈述起来更加复杂）。
Khot猜想，这一看似单纯的问题在某种意义上是难以近似问题的顶峰。
更确切地说，Khot的独一游戏猜想给出了如下相当技术性的命题：对于任何
，无论它的值多小，总存在一个色数k（可能相当大），使得对于k色数的约束网络，区分至少能满足
约束的网络和至多能满足
约束的网络是NP-难的。
因此，如果选择
，一定存在某个色数k，使得区分至少能满足99% 约束的网络和至多能满足1%约束的网络是NP-难（也就是说，实际上不可能）的。
乍一看，这似乎是一个不太可能的论断。直觉上来说，几乎能满足所有着色约束的网络应该跟几乎不能满足多少约束的网络看起来截然不同，也就不难找出它们之间的差异。然而当颜色数和网络大小达到亿计甚至万亿的水平，这一直觉突然就变得不那么一目了然了。
从这一猜想可以推论出，独一游戏着色问题无法以任何常数因子来有效近似（作为对比，回想一下，最小顶点覆盖问题可以轻松地近似到因子2。）为了说明其原因，我们将证明独一游戏问题无法近似到因子1/2。类似的推导（带有不同数字）也适用于你选择的任何其它因子。
因此，先假定我们能近似独一游戏到因子1/2——也就是说，我们可以给出一个有效算法，对于任何颜色数k和任意约束网络，它都可以生成一种网络着色，使得满足的约束数目至少是最佳着色的一半。
这一算法立刻会给予我们一种有效的方式来区分（比如说）至少能满足99%约束的网络和至多能满足1%约束的网络：对于前种网络，算法会生成满足至少（99/2）%也就是44.5%约束的着色方式，而对于后者，其本身特征决定了任何算法都无法给出满足超过1%约束的着色。因此，这样一种算法的存在会违背UGC。换句话说，假定UGC是对的，近似独一游戏问题到因子1/2——事实上到任意常数因子——是NP-难的。
这一推理就是所谓规约论证：我们把一个问题（区分99%和1%两种情形）规约到另一个问题（近似独一游戏问题到因子1/2），接着用前一问题的困难性来推断后一问题的困难性。规约是计算复杂性中证明困难性结果的标准方法。
或许源于Khot研究的着色问题的相对容易性，在他提出UGC之后的数年里，计算机科学家们开始注意到这一问题本身也有助于规约论证——比复杂的PCP定理更为显著。于是，它给予了研究者们一种方法对之前难以企及的问题做出困难性论证。
“UGC似乎囊括并简化了一些非常困难的技术性内容，”O’ Donnell称。
普适的困难性
UGC重要性的第一次凸显出现在2003年，当时Khot与特拉维夫大学及巴黎高等师范学院的Oded Regev证明，如果UGC成立，那么计算机科学家对最小顶点覆盖问题的直觉就是对的：要对这一问题近似到任何优于2的因子都是NP-难的。
两年后，UGC促成了一个真正惊人的发现，一个足以让计算机科学家慎重对待的发现。它涉及一个叫最大割的问题，指的是对于给定的网络，如何以适当的方式将顶点分成两个子集，使得这一分配割断尽可能多的边（也就是说，将边的两个端点分离到不同的子集里）。
1994年，麻省理工学院的Michael Goemans与康奈尔大学的David Williamson使用涉及三角函数等式的一种几何推导，得到了最大割的一种有效近似算法，可达到最佳割的
87%。斯坦福大学的Luca Trevisan称，大部分计算机科学家认为这一特殊数字是涉及的几何推导的人为产物，因此很可能还存在更好的近似算法，毕竟最大割本质上并非一个潜在的几何问题。Håstad已经在1999年证明近似最大割到超过94%会是NP-难的，但那还是留下了足够的余地去改进这一87%算法。
然而，到了2005年，Khot，O’ Donnell与耶路撒冷市希伯来大学的Guy Kindler及魏茨曼研究所的Elchanan Mossel证明，如果UGC成立，那么这一87%算法就是最大割的最佳有效近似。
“这是一个决定性时刻。从此独一游戏猜想变得举足轻重起来，”Trevisan说，“这一猜想给了我们精确答案——告诉我们这一来自几何分析的相当奇怪的常数是这个特定组合问题的最佳近似。”
自那以后，研究者们证明了大量类似这种形式的结果：‘如果UGC成立，那么问题X近似到优于因子Y是NP-难的’。接着在2008年，当时在华盛顿大学——如今在佐治亚理工学院——的Prasad Raghavendra证明UGC给出所有约束满足问题——像独一游戏这样力图满足给定约束集中尽可能多约束的问题——的精确困难性结果，从而一举震惊了计算机科学家们。“所有学科中的几乎所有问题都存在与此类似的版本，”Wigderson称。
此外，Raghavendra还证明UGC意味着任何这类问题的最佳近似都由一个非常简单的算法实现，在该算法中用到了被称为半正定规划的范式。
“这太了不起了，”Wigderson说道，“仅仅依靠Khot假定很难的一个问题，我们就立刻理解了无穷多问题的困难性。我觉得没有谁——包括他自己——想到过它会是如此普适的。”
原文链接：
https://www.simonsfoundation.org/2011/10/06/approximately-hard-the-unique-games-conjecture/
转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。
链接地址：https://wap.sciencenet.cn/blog-863936-1472103.html?mobile=1
收藏
