幾何学的複雑性理論

幾何学的複雑性理論 (GCT)は、ケタン・マルムリーとミリンド・ソホニによって提案された計算複雑性理論の研究プログラムです。このプログラムの目標は、複雑性クラスPが複雑性クラスNPと等しくないことを示すことによって、コンピュータサイエンスにおける最も有名な未解決問題である「 P = NP かどうか」に答えることです。

このアプローチの背後にある考え方は、代数幾何学と表現論（つまり、幾何学的不変理論）の高度なツールを採用して開発し、問題の下限を証明することです。現在、プログラムの主な焦点は代数的複雑性クラスにあります。パーマネントの計算が行列式の計算に効率的に還元できないことを証明することは、プログラムの主要なマイルストーンであると考えられています。これらの計算問題は、その対称性によって特徴付けられます。プログラムは、これらの対称性を利用して下限を証明することを目的としています。

このアプローチは、 PをNPから分離する現在実行可能な唯一のプログラムであると考える人もいます。しかし、ケタン・マルムリーは、このプログラムが実行可能であったとしても、 P対NP問題を解決するまでに約100年かかると考えています。^[1]

このプログラムは数学と理論計算機科学の研究者によって研究されています。このプログラムが注目される理由の1つは、このプログラムが相対化や一般下限値を証明する自然証明などの既知の障壁を回避するという議論が存在することです。^[2]

KD Mulmuley と M. Sohoni。「幾何学的複雑性理論 I: P 対 NP および関連問題へのアプローチ」SIAM J. Comput. 31(2), 496–526, 2001。

KD Mulmuley と M. Sohoni。「幾何学的複雑性理論 II: クラス多様体間の埋め込みに対する明示的な障害に向けて」SIAM J. Comput.、38(3)、1175–1206、2008 年。

KD Mulmuley、H. Narayanan、M. Sohoni。「幾何学的複雑性理論 III: Littlewood-Richardson 係数の非ゼロ性の決定について」J. Algebraic Combin. 36 (2012)、第 1 号、103–110 ページ。

KD Mulmuley. 幾何学的複雑性理論 V: ノイマン正規化のための効率的なアルゴリズム。J. Amer. Math. Soc. 30 (2017), no. 1, 225-309. arXiv:1209.5993 [cs.CC]

KD Mulmuley. 幾何学的複雑性理論 VI: 正値性による反転。、技術レポート、コンピューターサイエンス学部、シカゴ大学、2011 年 1 月。

• GCT ページ、シカゴ大学
• サイモンズ研究所のウェブページの説明
• cstheoryに関する GCT の質問
• ジョシュア・グロコウによる幾何学的複雑性理論のWikipedia風の説明
• 幾何学的複雑性理論の現在のブレークスルーは何ですか?
• https://mathoverflow.net/questions/243011/why-Should-algebraic-geometers-and-representation-theorists-care-about-geometric/