Sebuah pertanyaan tentang GCT

8

Dalam makalah 'Pada lenyapnya koefisien Kronecker' di sini di http://arxiv.org/pdf/1507.02955v1.pdf , ditunjukkan bahwa menentukan kepositifan koefisien kronecker pada umumnya sulit NP. Namun ada peringatan yang menyatakan bahwa hanya kepositifan 'koefisien Kronecker persegi panjang' diperlukan dalam GCT . Apa implikasi untuk GCT jika ini juga berubah menjadi NP sulit?

Pertanyaan terkait adalah apa konsekuensi GCT jika tidak ada rumus positif umum yang mirip dengan satu untuk kasus khusus koefisien LR?

cc.complexity-theory T ....
sumber

Jawaban:

10

Bahkan jika menentukan kepositifan koefisien Kronecker adalah NP-hard, atau bahkan jika tidak ada formula positif umum untuk mereka, masih mungkin bagi GCT untuk "bekerja." Bahkan di bawah asumsi sebelumnya, masih mungkin bahwa ada formula positif (dan bahkan prosedur keputusan polinomial waktu) untuk beberapa koefisien Kronecker persegi panjang. Jika seseorang dapat menemukan formula seperti itu, dan kemudian menunjukkan bahwa representasi irreducible yang sesuai muncul dengan multiplisitas nol di cincin koordinat penutupan orbit dari ukuran permanen yang sesuai, itu masih akan membuktikan dugaan (Kuat) Permanen versus Determinant.

Pembaruan 8/30/15 : Saya harus menambahkan bahwa, terlepas dari formula kombinatorial positif, saya pikir pendekatan geometrik untuk kompleksitas, seperti dalam GCT, adalah cara yang sangat berguna untuk memahami struktur kelas kompleksitas, dan menggunakan teori representasi di mana secara alami muncul (seperti di sini) selalu merupakan Ide Bagus. Karya Landsberg di bidang ini terkenal dalam arah ini (yaitu, menggunakan teknik geometris dikombinasikan dengan teori representasi, bahkan tanpa adanya formula kombinatorial positif). [akhiri pembaruan]

[Sekarang kembali ke rumus kombinatorial positif ...] Bahkan jika semakin banyak koefisien Kronecker berakhir menjadi NP-sulit untuk memutuskan lenyapnya mereka, atau jika tidak ada formula kombinatorial positif untuk mereka, (a) itu hanyalah sebuah bukti betapa sulitnya masalah ini (setelah semua, ketika GCT mengatasi kendala yang diketahui, masih bertujuan untuk membuktikan beberapa masalah yang sangat sulit terbuka), dan / atau (b) menunjukkan di mana harus mempersempit fokus seseorang agar GCT dapat bekerja (misalnya, seperti di atas).

Juga, meskipun kekerasan NP adalah "berita buruk" secara umum, itu belum tentu akhir dari jalan. Misalnya, meskipun Hamiltonian Cycle adalah NP-hard, masih ada banyak teorema dan pemahaman teoretis di sekitar siklus Hamilton. Kekerasan NP hanya membuat seseorang (atau setidaknya, saya) berharap bahwa tidak akan pernah ada "teori lengkap siklus Hamiltonian". Tapi kita tidak perlu "teori koefisien Kronecker lengkap" untuk membuktikan batas bawah melalui GCT - kita hanya perlu satu keluarga representasi yang menghilang pada penutupan orbit penentu tetapi tidak pada penutupan orbit permanen.

(Jawaban ini juga berlaku untuk makalah Kahle dan Michalek baru-baru ini yang menunjukkan bahwa ada keluarga multiplisitas plethysm yang tidak diberikan oleh jumlah titik bilangan bulat dalam keluarga poltop alami.)

Joshua Grochow
sumber
Apa yang terjadi jika sifat alami koefisien Kronecker persegi panjang yang seharusnya GCT eksis menjadi ternyata keras? Setelah semua ini adalah pertanyaan vs sini (hal-hal bisa menjadi bundar dan jelek). PNPVNPVP
T ....
2
Bahkan jika ternyata untuk setiap keluarga irrep yang muncul dengan multiplisitas nol di cincin koordinat penutupan orbit permanen, masalah keputusan Kronecker yang sesuai adalah NP-hard, (a) masih bisa ada pos. kombinasikan. rumus, dan (b) paragraf ketiga jawaban saya masih berlaku. Hal lain adalah: jika kita tahu fakta ini, kita mungkin akan tahu lebih banyak tentang irreps pada penutupan orbit perm daripada yang saat ini kita lakukan sehingga kita mungkin dapat menyelesaikan perm v det anyways .... PS - Email aku.
Joshua Grochow
bagaimana jika tidak ada formula kombinatorial yang positif sama sekali?
T ....
2
Jika tidak ada formula kombinatorial positif untuk Kronecker (atau multiplisitas dalam penutupan orbit det) untuk setiap irreps yang muncul dalam orbit perm perm orbit, itu masih tidak mengesampingkan GCT. Ini hanya berarti bahwa seseorang harus membuktikan sesuatu tentang multiplisitas ini dengan cara lain, misalnya secara geometris.
Joshua Grochow
1
Gagasan kasarnya adalah bahwa harus ada semacam analogi Hipotesis Riemann atas bidang terbatas (alias Weil Conjectures), tetapi terkait dengan kelompok kuantum yang tidak standar (seperti dalam GCT IV / VII / VIII). Sejauh yang saya tahu, bahkan muncul dengan pernyataan apa yang seharusnya analog ini masih terbuka ...
Joshua Grochow