Penjelasan gaya Wikipedia tentang Geometric Complexity Theory

Dapatkah seseorang memberikan penjelasan singkat tentang pendekatan GCT Mulmuley yang dapat dimengerti oleh non-pakar? Penjelasan yang cocok untuk halaman Wikipedia tentang topik tersebut (yang saat ini belum selesai).

Motivasi: Saya "membaca bersama" buku Scott Aaronson Quantum Computing sejak Democritus dengan seorang teman saya yang adalah seorang peneliti dalam teori string. Dalam kata pengantar buku, Aaronson menyebut GCT "teori string ilmu komputer". Menjadi ahli teori string, teman saya bersemangat tentang klaim ini dan bertanya apa itu GCT. Pada titik itu saya dengan malu-malu menyadari bahwa saya tidak punya jawaban siap-Wikipedia untuk pertanyaannya.

Saya tidak yakin level apa yang cocok untuk artikel Wikipedia (artikel yang berbeda tampaknya ditujukan untuk tingkat keahlian yang berbeda) atau tepatnya apa yang Anda cari. Jadi, inilah yang coba, tapi saya terbuka untuk umpan balik.

Teori kompleksitas geometri mengusulkan untuk mempelajari kompleksitas komputasi dari fungsi komputasi (katakanlah, polinomial) dengan mengeksploitasi simetri yang melekat dalam kompleksitas dan setiap simetri tambahan dari fungsi yang sedang dipelajari.

Seperti banyak pendekatan sebelumnya, tujuan utamanya adalah untuk memisahkan dua kelas kompleksitas dengan menunjukkan bahwa ada polinom yang mengambil fungsi sebagai input (katakanlah , dengan koefisien vektor mereka) sehingga menghilang pada setiap fungsi tetapi tidak hilang pada beberapa fungsi . pfpf∈ C e a s y g h a r d ∈ C h a r $\mathcal{C}_{easy}, \mathcal{C}_{hard}$$p$$f$$p$$f \in \mathcal{C}_{easy}$$g_{hard} \in \mathcal{C}_{hard}$

Gagasan kunci pertama (lih. [GCT1, GCT2]) adalah menggunakan simetri untuk mengatur bukan fungsi itu sendiri, tetapi untuk mengatur properti ( algebro-geometrik ) dari fungsi-fungsi ini, seperti yang ditangkap oleh polinomial seperti$p$ atas. Ini memungkinkan penggunaan teori representasi dalam berusaha menemukan . Gagasan serupa yang berkaitan dengan teori representasi dan geometri aljabar telah digunakan dalam geometri aljabar sebelumnya, tetapi setahu saya tidak pernah seperti itu.$p$

Gagasan kunci kedua (lih. [GCT6]) adalah menemukan algoritma kombinatorial (dan waktu polinomial) untuk masalah representasi-teoretik yang dihasilkan, dan kemudian merekayasa balik algoritme ini untuk menunjukkan bahwa ada. Ini dapat diambil dalam semangat menggunakan Linear Programming (suatu algoritma) untuk membuktikan pernyataan murni kombinasi tertentu.$p$

Memang, [GCT6] menyarankan pengurangan masalah representasi-teori di atas menjadi masalah Pemrograman Integer , kemudian menunjukkan bahwa IP yang dihasilkan diselesaikan dengan relaksasi LP mereka, dan akhirnya memberikan algoritma kombinatorial untuk LP yang dihasilkan. Dugaan dalam [GCT6] sendiri termotivasi oleh hasil rekayasa balik yang diketahui untuk koefisien Littlewood-Richardson, masalah analog tetapi lebih mudah dalam teori representasi. Dalam kasus koefisien LR, aturan kombinatorial Littlewood-Richardson adalah yang pertama. Kemudian Berenstein dan Zelevinsky [BZ] dan Knutson dan Tao [KT] (lihat [KT2] untuk ikhtisar yang bersahabat) memberikan IP untuk koefisien LR. Knutson dan Tao juga membuktikan dugaan saturasi, yang menyiratkan bahwa IP diselesaikan dengan relaksasi LP-nya (lih. [GCT3, BI]).

Hasil dari [GCT5] menunjukkan bahwa secara acak derandomisasi Normalisasi Lemma Noether pada dasarnya setara dengan masalah terbuka yang terkenal dalam teori kompleksitas derandomisasi kotak hitam pengujian identitas polinomial . Secara kasar bagaimana hal ini cocok dengan program yang lebih besar adalah bahwa menemukan basis eksplisit untuk fungsi yang (tidak) menghilang pada C e a s y (dalam hal ini, kelas yang penentunya lengkap) dapat digunakan untuk memperoleh suatu aturan kombinatorial untuk masalah yang diinginkan dalam teori representasi, seperti yang telah terjadi di pengaturan lain dalam geometri aljabar. Langkah menengah di sini adalah menemukan dasar untuk hal - $p$$\mathcal{C}_{easy}$$p$yang (tidak) hilang pada normalisasi , yang dengan konstruksi varietas aljabar yang lebih baik - dengan kata lain, untuk derandomisasi Lemma Normalisasi Noether untuk DET.$\mathcal{C}_{easy}$

Contoh simetri kompleksitas dan fungsi

Misalnya, kompleksitas fungsi - untuk sebagian besar pengertian kompleksitas alami - tidak berubah jika kita mengubah variabel f ( x π ( 1 ) , ... , x π ( n ) ) oleh beberapa permutasi π . Jadi permutasi adalah simetri kompleksitas itu sendiri. Untuk beberapa pengertian kompleksitas (seperti dalam kompleksitas rangkaian aljabar) semua perubahan linear yang tidak dapat dibalik dari variabel-variabel adalah simetri.$f(x_1, \dotsc, x_n)$$f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$$\pi$

det ( A X B ) = det ( X T ) = det ( X ) A , B det ( A B ) = $\det(X)$$\det(AXB) = \det(X^{T}) = \det(X)$$A,B$$\det(AB) = 1$

Beberapa Kemajuan Terbaru [bagian ini jelas tidak lengkap dan lebih teknis, tetapi akun lengkap akan memakan waktu puluhan halaman .... Saya hanya ingin menyoroti beberapa kemajuan terbaru]

Burgisser dan Ikenmeyer [BI2] menunjukkan batas bawah lebih rendah pada perkalian matriks mengikuti program GCT sejauh menggunakan representasi dengan multiplisitas nol vs bukan nol. Landsberg dan Ottaviani [LO] memberikan batas bawah paling dikenal pada dasarnya pada peringkat perbatasan perkalian matriks menggunakan teori representasi untuk mengatur properti aljabar, tetapi tidak menggunakan multiplikasi representasi atau aturan kombinatorial.2n$\frac{3}{2}n^2$$2n^2$

Masalah berikutnya setelah koefisien Littlewood-Richardson adalah koefisien Kronecker . Ini muncul baik dalam serangkaian masalah yang diduga pada akhirnya mencapai representasi-teori masalah yang timbul dalam GCT, dan lebih langsung sebagai batas pada multiplisitas dalam pendekatan GCT untuk penggandaan matriks dan permanen versus determinan. Menemukan aturan kombinatorial untuk koefisien Kronecker adalah masalah terbuka lama dalam teori representasi; Blasiak [B] baru-baru ini memberikan aturan kombinatorial untuk koefisien Kronecker dengan satu bentuk kait.

Kumar [K] menunjukkan bahwa representasi tertentu muncul dalam cincin koordinat dari determinan dengan multiplisitas bukan-nol, dengan asumsi dugaan kolom kolom Latin (lih. Huang-Rota dan Alon-Tarsi; dugaan ini juga, mungkin tidak secara kebetulan, muncul di [BI2 ]). Karenanya representasi ini tidak dapat digunakan untuk memisahkan permanen dari determinan atas dasar kelipatan nol vs bukan nol, meskipun masih mungkin untuk menggunakannya untuk memisahkan permanen dari determinan dengan ketidaksetaraan yang lebih umum antara multiplisitas.

Referensi [B] J. Blasiak. Koefisien Kronecker untuk satu bentuk kait. arXiv: 1209.2018, 2012.

[BI] P. Burgisser dan C. Ikenmeyer. Algoritma max-flow untuk kepositifan koefisien Littlewood-Richardson. FPSAC 2009.

[BI2] P. Burgisser dan C. Ikenmeyer. Batas Bawah Eksplisit melalui Teori Kompleksitas Geometris. arXiv: 1210.8368, 2012.

[BZ] AD Berenstein dan AV Zelevinsky. Multiplisitas tiga untuk dan spektrum aljabar eksterior dari representasi adjoint. $\mathfrak{sl}(r+1)$J. Algebraic Combin. 1 (1992), no. 1, 7–22.

[GCT1] KD Mulmuley dan M. Sohoni. Teori Kompleksitas Geometrik I: Suatu Pendekatan terhadap P vs NP dan Masalah Terkait. SIAM J. Comput. 31 (2), 496-526, 2001.

[GCT2] KD Mulmuley dan M. Sohoni. Teori Kompleksitas Geometris II: Menuju Penghalang Eksplisit untuk Penyuluhan antar Varietas Kelas. SIAM J. Comput., 38 (3), 1175–1206, 2008.

[GCT3] KD Mulmuley, H. Narayanan, dan M. Sohoni. Teori kompleksitas geometri III: tentang penentuan tidak berlebihnya koefisien Littlewood-Richardson. J. Algebraic Combin. 36 (2012), no. 1, 103–110.

[GCT5] KD Mulmuley. Teori Kompleksitas Geometrik V: Kesetaraan antara derandomisasi blackbox dari pengujian identitas polinomial dan derandomisasi Lemma Normalisasi Noether. FOCS 2012, juga arXiv: 1209.5993.

[GCT6] KD Mulmuley. Teori Kompleksitas Geometrik VI: flip via positif. , Laporan Teknis, departemen Ilmu Komputer, Universitas Chicago, Januari 2011.

[K] S. Kumar. Studi representasi yang didukung oleh penutupan orbit dari determinan. arXiv: 1109.5996, 2011.

[LO] JM Landsberg dan G. Ottaviani. Batas bawah baru untuk peringkat perbatasan perkalian matriks. arXiv: 1112.6007, 2011.

[KT] A. Knutson dan T. Tao. Model honeycomb dari produk tensor . I. Bukti dugaan saturasi. $\text{GL}_n(\mathbb{C})$J. Amer. Matematika Soc. 12 (1999), no. 4, 1055–1090.

[KT2] A. Knutson dan T. Tao. Sarang lebah dan jumlah matriks Hermitian. Pemberitahuan Amer. Matematika Soc. 48 (2001), no. 2, 175–186.

Saya baru-baru ini memberikan jawaban untuk pertanyaan terkait tentang Mathoverflow https://mathoverflow.net/questions/277408/what-are-the-current-breakthroughs-of-geometric-complexity-theory

Karena situs ini mungkin tempat yang lebih baik, izinkan saya mengulangi jawaban itu di bawah. Referensi ke Joseph atau Timotius adalah tentang posting lain untuk pertanyaan MO itu.

---

$X=(X_{ij})_{1\le i,j\le n}$$n\times n$$F_1(X)={\rm det}(X)$$n$

$$F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right]$$ $m\times m$$n$$X_{11}$$X_{nn}$ $$c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \}$$ $G$$GL(n^2)$$n^2$$X$$\overline{G\cdot F_i}$${\rm P}\neq{\rm NP}$$c(m)$$m$

$\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$$G$

$$\mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d$$ $d$$n$$m$$\lambda$ $${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)$$ $${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)>{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ .$$

$\lambda$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$. Harapan ini telah tergencet dalam karya Bürgisser, Ikenmeyer dan Panova yang disebutkan oleh Timothy. Namun, kemungkinan penghalang multiplisitas masih terbuka.

$F_1$$F_2$$m$$G$$\lambda$$n^2$$X$

$F_1$$F_2$$G=SL(2)$

$$F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4$$ $$F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ .$$ $F$ $$H(F)(x,y)=\frac{\partial^2 F}{\partial x^2}\frac{\partial^2 F}{\partial y^2}-\left( \frac{\partial^2 F}{\partial x\partial y} \right)^2\ .$$ $x,y$$F=F_1$$F=F_2$

Jadi, sebuah "rencana" superoptimis yang mungkin untuk GCT melibatkan urutan langkah-langkah berikut.

1) Temukan cara untuk menghasilkan ton yang bersamaan.

$F_1$

$F_2$

$GL(n^2)$$GL(n)\times GL(n)$$GL(n^2)$$GL(n^2)$$GL(n)\times GL(n)$$SL(n(n+1)/2)$$SL(n)$

${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$$F_1$

$F_1$terlalu). Menurut pendapat saya, orang perlu membuat kemajuan pada pertanyaan semacam itu ( Teorema Empat Warna juga dari jenis ini, melalui pengurangan karena Kauffman dan Bar-Natan) sebelum Valiant's Conjecture.

$c(m)$

$$\left(\begin{array}{c}2m\\ m \end{array}\right)-1\ .$$

PS: Saya harus menambahkan bahwa pesimisme saya khusus untuk Hipotesis Valiant yang merupakan `Hipotesis Riemann 'di lapangan. Tentu saja, seseorang tidak boleh melempar bayi dengan air mandi dan merendahkan GCT karena sejauh ini gagal membuktikan dugaan ini. Ada banyak masalah yang lebih mudah didekati di bidang ini di mana kemajuan telah dibuat dan lebih banyak kemajuan diharapkan. Lihat khususnya artikel yang disebutkan di atas oleh Grochow dan ulasan oleh Landsberg.

GCT adalah program penelitian untuk membuktikan teori kompleksitas yang terikat dan dengan cara menentang abstrak / ringkasan gaya wikipedia karena abstraksi yang berat, tetapi untuk kerumunan TCS survei yang baik tersedia. [2] [3] [4] (dan tentunya Wikipedia adalah tempat terbaik untuk entri wikipedia). itu dirumuskan pada awal 2000-an oleh Mulmuley dan keduanya relatif baru dalam teori kompleksitas dan sangat maju, menggunakan dan menerapkan matematika canggih (aljabar geometri) yang tidak berasal dari teori kompleksitas / TCS.

pendekatan ini dianggap menjanjikan oleh beberapa tetapi mungkin terlalu rumit oleh otoritas lain yaitu tidak terbukti dan oleh karena itu kontroversial apakah dapat mengatasi "hambatan" yang dikenal standar. (dalam hal ini ia menunjukkan beberapa tanda dari apa yang disebut "pergeseran paradigma" Kuhn.). Bahkan Mulmuley mengusulkan bahwa secara realistis mungkin tidak akan berhasil (dalam membuktikan pemisahan kelas kompleksitas utama) setelah beberapa dekade pengembangan lebih lanjut. di sini adalah pendapat skeptis oleh Fortnow, otoritas terkemuka di bidang teori kompleksitas: [1]

Pertimbangkan gunung besar dan Anda ingin mencapai puncak gunung. Ketan datang dan berkata dia akan mengajarimu cara membuat alat yang dibutuhkan untuk mendaki gunung. Butuh waktu satu bulan belajar dan sebenarnya alat ini tidak cukup baik untuk mendaki gunung. Mereka perlu ditingkatkan dan perbaikan ini tidak akan terjadi dalam hidup Anda. Tetapi tidakkah Anda ingin belajar bagaimana orang lain akan mendaki gunung berabad-abad dari sekarang?

[1] Cara membuktikan NP berbeda dari blog P Fortnow

[2] Memahami Pendekatan Mulmuley-Sohoni pada P vs NP Regan

[3] Pada Teori P vs. NP dan Kompleksitas Geometris Mulmuley

[4] Program GCT menuju masalah P vs NP Mulmuley