二部グラフマッチングはNCクラスに属する！

スコット・アーロンソンのブログShtetl-Optimized このブログから他に何も得られなかったとしても：量子コンピュータはすべての解を並列に試すだけで難しい問題を瞬時に解決するわけではない。 « T-Rexを信用するな QCに関するホワイトハウスの行政命令に対する私の回答 » 二部グラフマッチングはNCクラスに属する！ 今日は機嫌が良いので—子供たちと一緒にカリフォルニア州ビッグベア湖近くの山奥にある美しい科学キャンプにいる—何かポジティブなことについてブログを書こうと思った。 先週、5人の著者（Chatterjee、Ghosh、Gurjar、Raj、Thierauf）がElectronic Colloquium on Computational Complexityに主要な論文を投稿した。この論文は、二部グラフマッチング問題が複雑性クラスNCに属することを示す（あるいは、少なくとも信用できる形で示すと主張する）ものである。これがもし確定すれば、1980年代から未解決だった並列アルゴリズムと脱ランダム化における中心的な問題が解決されることになる。 二部グラフマッチングでは、n人の男性とn人の女性のリストが与えられ、誰が誰とデートする意思があるかが伝えられ、全員を希望する相手とペアにできるかどうか、そしてもしできるなら実際にペアにするという目標が与えられる。組合せアルゴリズムの偉大な初期の発見の一つで、すべての入門アルゴリズムコースで教えられているのは、この問題がnについて多項式時間で解けるということである。これは、素朴な総当たりアプローチではn!通りの可能性を調べる必要があるにもかかわらずである。（二部グラフ版では、男性と女性は全員ストレートであると仮定する。男性と女性がLGBTである可能性がある場合、一般グラフのマッチング問題となるが、これも多項式時間で解けることが判明している。ただし、そのアルゴリズムははるかに洗練されており、1960年代のエドモンズによる主要な発見であった。） いずれにせよ、問題は多項式時間よりもさらに良くできるか、特に、多項式個の並列プロセッサが与えられた場合に、log(n)の多項式時間で問題を解決できるかということである。1980年代には、まずKarp、Upfal、Wigdersonが、次に（非常に異なる方法で）Mulmuley、私の元博士課程の指導教員であるUmesh Vazirani、そしてUmeshの兄弟であるVijay Vaziraniが、答えはイエスであると示すことに成功した。しかし、これは並列プロセッサが追加でランダムビットにアクセスでき、高い確率で成功するだけで良い場合に限られていた。 今回の新しい成果は、Mulmuley-Vazirani-Vaziraniアルゴリズムを脱ランダム化し、上記の1と2の問題がどちらも並列処理を用いて決定論的な多項式対数時間で解決可能であることを示すものだ（言い換えれば、複雑性クラスNCに属する）。 いいや、私にはまだそれがどのように機能するのか理解できない。もし誰か理解している人がいたら、コメントで自由に説明してほしい！あるいは、お気に入りのAIに要約を生成するように頼んでもいい。もし選択肢がなくなったら、いつか実際に論文を読んでみるかもしれない。（注：この投稿の以前のバージョンに対するいくつかの修正について、Gil Kalaiに感謝します。） もう一つお知らせ：今日はNYCの予備選挙の日だ！AIガバナンスと安全性に取り組む私の最も賢い友人のほぼ全員が、Alex Boresの議会キャンペーンに非常に興奮している—実際、彼らは彼を人類の最後の最高の希望と考えていると言っても過言ではないだろう。BoresはAI規制を試みる全国的なリーダーであり、Marc Andreessenの「Leading the Future」という反AI規制PACが彼の立候補を妨害するために数百万ドルを費やしているほどだ。AI以外では、Boresはまともな、従来の民主党員、つまり私が好きなタイプであり、イスラエルに関する彼の支持層よりもはるかに穏健である（主要な対立候補もそうであることに注意）。あらゆる問題に関するBoresの見解についてはコメントしないが、ただこう言わせてほしい：もしあなたがニューヨーク州第12下院選挙区（マンハッタン中心部の広大な部分を含む）に住んでいて、AIの安全性に関心があるなら、まだ間に合ううちにBoresへの投票を検討してほしい。 フォロー このエントリーは2026年6月22日月曜日午後12時27分に投稿され、お知らせ、複雑性カテゴリに分類されています。このエントリーへの返信はRSS 2.0フィードでフォローできます。返信を残すか、ご自身のサイトからトラックバックすることができます。 「二部グラフマッチングはNCクラスに属する！」への25件の返信 Nabamのコメント：#1 2026年6月22日午後2時07分 これでようやく理解できるかもしれない。あなたは、教皇やOlah、Anthropicについての論争や、人間の無関係さに対する憂鬱な見方にもかかわらず、AIは規制されなければならないと本当に主張しているのですね。そして、それは非常に安心できる立場です。なぜなら、残念ながら、（一見して）そう見えるのとは裏腹に、「数学の自動化」というPRの売り込みは、証明上不可能ではありません。それは「ただ」証明上反証不可能であるだけです（ある種のコルモゴロフ複雑性やチャイティン数のヨガによれば、AIが証明したものが、ある程度無視できないほど入力に隠されており、人間の数学研究者を「オフ」にしても「更新」されないという考えを反駁するのは誰にとっても難しいでしょう。その逆も誰も排除できません）。結構。だからPRは科学ではない。驚き！むしろ、それは「技術的に利用可能な核融合は間近である」とか、1970年代からの私のお気に入りの「我々はペーパーレスオフィスに近づいている！それはあっという間にやってくるだろう」といったものと同類です。あるいは、もし望むなら、来世に関する素朴な約束と比較してもいいでしょう。しかし、ここに落とし穴があります。教皇や教会でさえ、それで逃げ切ることはできませんでした。少なくともベータ版では。現在の教皇はそれを覚えていたに違いありません。いや。加速主義者は無敵ではありません。そして、数学が自動化されようとしているわけでもありません。それを証明できるか？いいえ。私がマーズに大気、プレートテクトニクス、磁場、火山活動を導入しないことをイーロン・マスクが証明できないのと同じです。あるいは、私がアンドリーセンのファンである平行宇宙が存在しないことも証明できません。これは人間であることの意味を思い出す良い機会です。そしてそれは、教皇の回勅「Magnifica humanitas」に書かれているからといって、その真実性が劣るわけではありません。 Hamish Peter Toddのコメント：#2 2026年6月22日午後3時16分 やった、アルゴリズムの投稿だ！ Danのコメント：#3 2026年6月22日午後3時49分 NY-12の有権者です—うわー、私の投票が連邦レベルで実際に意味を持つのは、これまでで初めてだと思います。これもまた、私が先行する両候補者を心から好むという本当に稀なケースなので、決断は非常に難しかったです。しばらくの間Lasherに傾いていましたが、OpenAI/a16zが私を攻撃するために集中砲火した広告の息をのむような不誠実さのために、最終的にはBoresに投票することにしました。Lasherが勝っても構いませんでしたが、ここでLeading The Futureの行動に報いることはできないと感じました。 Yeyuan Chenのコメント：#4 2026年6月22日午後4時39分 それは本当にエキサイティングな結果で、それについて2つの興味深いことをコメントしたい。この論文は、私たちの最近の研究「From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids」（STOC2026）に触発されています。私たちの論文は、符号理論の中心的な組み合わせオブジェクトである部分空間設計に関するものです。実際、二部グラフマッチングと私たちの研究との間のつながりを見つけることは非常に非自明な観察ですが、もしそれがヒントとして与えられれば、残りの技術的な作業はそれほど難しくないと感じます。それは、Ryanが木評価の画期的な発見が時間空間シミュレーションにつながるのを見つけたのと同様の知恵です。少し宣伝：このつながりやアイデアがどこから来たのか知りたい場合は、木曜日にSTOCで行われるこの論文についての私の講演にぜひお越しください。穏やかな紹介を試みます。二部グラフマッチングアルゴリズムがどのように機能するかを説明します。もう一つの興味深いこと：プレプリントが投稿される前に、著者がワークショップでそれを最初に発表し、私はそれについて聞いていたので、この結果を知っていました。そして、彼らの研究が私たちの研究に触発されたものであることを知った後、私は彼らの最初の主要な結果を再現することができました。繰り返しになりますが、つながりの存在が与えられれば、残りの部分は難しくないと感じます。次に、GPT5.5proに、私たちの論文とのつながりが与えられた場合にそれを再現できるかどうかをテストしました。GPTが成功すると予想しましたが、失敗しました！驚きましたが、今回は人類の成功だと言っておきましょう（一時的かもしれませんが）。著者の皆さんに心からの祝福を！プロンプトの内容