幾何複雜性理論是什麼？

wiki詞條為：Geometric complexity theory

這個理論和傳統計算複雜性理論有何不同或聯繫，它是如何用到代數幾何知識的？

---

更新1: 掃了一眼那兩個 talk, 其實只是在講一個例子: 找和某個 permanent 一樣難算的 determinant: 我們知道 determinant 並且 permanent-hard. 那麼除了證明本身, 如何刻畫這兩個問題在計算困難程度上的巨大區別呢? 一個想法是, 對於 permanent 找一個和它一樣難算的 determinant, 顯然後者的維度會是前者的指數級別.

證明這一結果的 bound 可以通過圖論或者幾何的手段. 這裡提到的幾何方法就是從 permanent 和 determinant 的零點(幾何)分別開始考慮, 看到這裡就有點代數幾何的意味了......看起來很有趣, 有空看了再更.

--------------------------------------------------------

謝 @月隱汐邀，然而我基本沒了解過。simons 之前的一個 program 和這個相關：

Algorithms and Complexity in Algebraic Geometry

boot camp 裡面有兩講 introduction to geometry complexity theory：

Simons Institute for the Theory of Computing

其中還有個 workshop 整個都是 geometric complexity theory.

需要說明的是，要看的話最好科學上網看youtube，上面給的下載鏈接應該是1080p的。另外，一般 simons 的 program 裡面第一部分 boot camp 都是給大同行講的，所以相對來說還能看，不會過於technical。

---

要了解幾何複雜性理論，最好是參考創始人芝加哥大學計算機系教授Ketan Mulmuley的著作。以下是他著作的鏈接（全文下載）：http://gct.cs.uchicago.edu/

Ketan Mulmuley在 Geometric Complexity Theory: Introduction 一文中介紹了他的整個研究綱領。幾何複雜性理論（GCT）的目的是利用代數幾何與表示論證明。整個的過程如下圖：

---

推薦閱讀：