二分图匹配属于 NC

# 二分图匹配属于NC复杂度类！ 来源：https://scottaaronson.blog/?p=9851 今天心情不错——我和孩子们在加州大熊湖附近的山间，参加一个美丽的科学夏令营——因此我想写点积极的东西。上周，五位作者（Chatterjee、Ghosh、Gurjar、Raj 和 Thierauf）向《计算复杂性电子讨论会》提交了一篇**重要论文**（https://eccc.weizmann.ac.il/report/2026/100/），该论文表明（或者说，至少可信地声称表明）：**二分图匹配**（https://discrete.openmathbooks.org/dmoi3/sec_matchings.html）问题属于复杂度类 **NC**（https://en.wikipedia.org/wiki/NC_(complexity)）。如果这一结果成立，它将解决一个自20世纪80年代以来一直悬而未决的并行算法与去随机化领域的核心问题。 在二分图匹配问题中，给定n个男性和n个女性的列表，以及谁愿意与谁约会的信息，你的目标是： 1. 判断是否可能让每个人都与一位自愿的伴侣配对； 2. 如果可能，实际找出这样一组配对。 组合算法早期最伟大的发现之一——每个算法入门课程都会教授——是这个问题可以在关于n的多项式时间内求解，尽管天真的暴力方法需要检查n!种可能性。 （注意：在**二分图**版本中，我们假设男性和女性都是异性恋。如果允许同性恋，我们就得到**一般图**中的匹配问题，同样可以在多项式时间内求解，但算法要复杂得多，是埃德蒙兹在20世纪60年代的一项重大发现。） 无论如何，问题是：我们能否做到比多项式时间更好？具体来说，给定多项式数量的并行处理器，我们能否在多对数时间（即关于log(n)的多项式时间）内解决这个问题？ 回到20世纪80年代，先是 **Karp、Upfal 和 Wigderson**（http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/KUW86/KarpUW86.pdf），随后（通过一种非常不同的方法）**Mulmuley**、我以前的博士生导师 **Umesh Vazirani** 以及 Umesh 的兄弟 **Vijay Vazirani** 成功**证明**答案是肯定的（https://people.eecs.berkeley.edu/~vazirani/pubs/matching.pdf），但前提是并行处理器额外获得随机比特，并且只需要以高概率成功。 新的成就是**去随机化** Mulmuley-Vazirani-Vazirani 算法，并证明上述问题1和问题2都可以在**确定性的**并行多对数时间内求解——换句话说，属于复杂度类 **NC**。 不，我还不了解它的工作原理。如果有人了解，欢迎在评论中解释！或者让你最喜欢的AI生成一个摘要。如果别无他法，我可能最终会尝试**阅读论文**。 （*注：*感谢 Gil Kalai 对本文早期版本的一些指正。） --- **另一项公告：**今天是纽约市的初选日！几乎所有我在人工智能治理与安全领域最聪明的朋友都对 **Alex Bores**（https://www.alexbores.nyc/）的国会竞选活动感到极度兴奋——毫不夸张地说，他们认为这是人类最后的希望。Bores 在试图监管人工智能方面一直走在全国前列，以至于 Marc Andreessen 的“引领未来”反AI监管政治行动委员会（PAC）花费了数百万美元试图扼杀他的候选人资格。在人工智能之外，Bores 看起来是一位理智、传统的民主党人——也就是我喜欢的那种——并且在他对以色列的立场上比他的基本盘温和得多（注意他的主要对手也是如此）。我不对 Bores 在所有问题上的观点发表评论，只想简单说：如果你住在 **纽约第12国会选区**（https://en.wikipedia.org/wiki/New_York%27s_12th_congressional_district）（包括曼哈顿中心的大片区域），并且关心人工智能安全，请在还有时间时考虑投票给 Bores。 这篇博文发布于 2026年6月22日星期一下午12:27，归类于 **公告**（https://scottaaronson.blog/?cat=31）和 **复杂性**（https://scottaaronson.blog/?cat=5）。你可以通过 **RSS 2.0**（https://scottaaronson.blog/?feed=rss2&p=9851）订阅这篇博文的回应。你可以在本站 **留下回应**（https://scottaaronson.blog/?p=9851#respond），或者从你自己的网站 **引用**（https://scottaaronson.blog/wp-trackback.php?p=9851）本文。 你可以在评论中使用富文本HTML！你也可以使用基本 TeX，通过将公式用 $$ $$ 括起来表示显示公式，或用 \\( \\) 表示内联公式。 在经历了二十多年基本开放的评论后，*Shtetl-Optimized* 于2024年7月过渡到以下政策： 所有评论默认被视为发送给我 Scott Aaronson 的个人信息——既不期望它们会出现在博客上，也不期望我会回复它们。 我会在闲暇时酌情决定，并与 *Shtetl-Optimized* 守护委员会（https://scottaaronson.blog/?p=6576）协商，挑选出我认为特别有趣或能推动话题发展的评论发布在博客上，并尽量回答这些问题。但这更像是“致编辑的信”。任何觉得受到不公正审查的人都可以自由使用互联网的其他部分。