HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Bipartite Matching Is in NC (scottaaronson.blog)

64 pointsby amichail4 コメント

要約

最近の研究で、二部グラフマッチング問題が複雑性クラスNCに属することが示されました。これは、1980年代から未解決だった並列アルゴリズムと脱ランダム化における中心的な問題を解決するものです。筆者はこの成果に喜びを表明し、ニューヨークの選挙に関する別件の告知も行っています。

全文翻訳

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

今日は気分が良いので――子供たちと一緒に、カリフォルニアのビッグベア湖の近くの美しい科学キャンプにいます――何かポジティブなことについてブログを書こうと思いました。先週、5人の著者(Chatterjee、Ghosh、Gurjar、Raj、Thierauf)が計算複雑性に関する電子会議録に画期的な論文を投稿しました。この論文は、二部マッチング問題が計算複雑性クラスNCに属することを示す(あるいは、少なくともそのように主張する)ものです。これが正しいと仮定すれば、1980年代から未解決だった並列アルゴリズムと決定論的計算の中心的な問題を解決することになります。

二部マッチングでは、n人の男性とn人の女性のリストが与えられ、誰が誰と交際を望んでいるかが示され、目標は以下の2つです。

  1. 全員が希望する相手とペアになれるかどうかを判断する。
  2. もし可能であれば、実際にペアを作る。

組合せアルゴリズムの初期の偉大な発見の一つであり、あらゆる入門アルゴリズムコースで教えられているのは、この問題はnの多項式時間で解けるということです。たとえ素朴な総当たりアプローチではn!通りの可能性を調べる必要があるとしてもです。

(二部バージョンでは、男性と女性はすべて異性愛者であると仮定します。もし男性と女性がLGBTである場合、一般的なグラフでのマッチング問題になりますが、これも多項式時間で解けることが判明していますが、アルゴリズムははるかに洗練されており、1960年代のエドモンズによる大きな発見でした。)

いずれにせよ、問題は多項式時間よりもさらに良い時間、具体的には、多項式個の並列プロセッサが与えられた場合に、log(n)の多項式時間で問題を解けるかどうかということです。

1980年代に、まずKarp、Upfal、Wigdersonが、そして(非常に異なる方法で)私の元博士課程指導教員であるUmesh VaziraniとUmeshの兄弟であるVijay Vaziraniが、並列プロセッサが追加で乱数ビットにアクセスでき、高い確率で成功すればよい場合に、答えが「はい」であることを示すことに成功しました。

今回の新しい成果は、Mulmuley-Vazirani-Vaziraniアルゴリズムを決定論的にし、上記の1と2の問題の両方が、並列処理を用いて決定論的な多対数時間(つまり、NC計算複雑性クラス)で解けることを示すことです。

いいえ、まだ仕組みは理解できていません。もし誰か理解している人がいれば、コメントで説明してください!あるいは、お気に入りのAIに要約を生成させてください。選択肢がなくなったら、いつか実際に論文を読んでみようと思います。

(注:この投稿の以前のバージョンに関するいくつかの修正について、Gil Kalaiに感謝します。)


もう一つの告知: 今日はニューヨーク市で予備選挙の日です!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フィードでフォローできます。あなたは返信を残すことや、自分のサイトからトラックバックすることができます。

コメントでリッチHTMLを使用できます!表示される数式には$$ $$、インライン数式には( )で囲むことで、基本的なTeXも使用できます。

20年近くほぼオープンだったコメント欄を経て、2024年7月にShtetl-Optimizedは以下のポリシーに移行しました:

すべてのコメントは、デフォルトで私、Scott Aaronsonへの個人的なメッセージとして扱われ、ブログに掲載されるか、私が返信するかのどちらかの期待はありません。

私の裁量と判断により、Shtetl-Optimized保護者委員会と協議の上、特に興味深い、またはトピックを進展させると私が判断したコメントを厳選してブログに掲載し、それらにはできる限り返信します。しかし、それは「編集者への手紙」のようなものになるでしょう。不当に検閲されたと感じる人は、インターネットの他の場所へどうぞ。