Bagaimana pendekatan geometris Mulmuley-Sohoni untuk menghasilkan batas bawah menghindari menghasilkan bukti alami (dalam pengertian Razborov-Rudich)?

Ungkapan tepat dari judul adalah karena Anand Kulkarni (yang mengusulkan situs ini dibuat). Pertanyaan ini diajukan sebagai contoh pertanyaan, tetapi saya sangat ingin tahu. Saya tahu sedikit tentang geometri aljabar, dan pada kenyataannya juga hanya memiliki sepintas, pemahaman sarjana tentang hambatan yang dimainkan dalam pertanyaan P / poly versus NP (non-relativizing, non-algebrazing, kemungkinan tidak akan menjadi bukti alami) .

Apa yang membuat geometri aljabar tampak seperti itu dapat melewati rintangan semacam ini? Apakah itu hanya intuisi ahli lapangan atau apakah kita memiliki alasan yang sangat bagus untuk percaya bahwa pendekatan ini secara fundamental lebih kuat daripada pendekatan sebelumnya? Apa hasil yang lebih lemah yang dapat dicapai oleh pendekatan ini?

[Saya akan menjawab pertanyaan seperti yang disebutkan dalam judul, meninggalkan litani pertanyaan lain tentang GCT untuk utas lainnya.] Membuktikan dugaan yang muncul dalam GCT sepertinya akan sangat menggunakan fakta bahwa fungsi-fungsi tersebut sedang dipertimbangkan (determinan dan permanen, dan polinomial terkait lainnya untuk P / poli dan NP) dicirikan oleh simetri mereka. Kebutuhan ini bukanlah hasil formal, tetapi intuisi yang diungkapkan oleh beberapa ahli. (Pada dasarnya bahwa tanpa adanya karakterisasi oleh simetri, memahami geometri aljabar dan teori representasi yang muncul jauh lebih sulit.)

Ini harus memotong Razborov-Rudich karena sangat sedikit fungsi yang ditandai oleh simetri mereka (melewati kondisi kebesaran dalam definisi bukti alami). Sekali lagi, saya belum melihat bukti tentang ini, tetapi ini adalah intuisi yang saya dengar diungkapkan oleh beberapa ahli.

Sekarang, atas bilangan kompleks, tidak jelas bagi saya bahwa ada analog dari Razborov-Rudich. Meskipun sebagian besar GCT saat ini berfokus pada bilangan kompleks, ada analog dalam karakteristik hingga (dijanjikan dalam makalah GCT VIII yang akan datang). Dalam karakteristik yang terbatas, orang mungkin benar-benar dapat membuktikan pernyataan dari bentuk "Sangat sedikit fungsi yang ditandai oleh simetri mereka."

[Menanggapi komentar Ross Snider, inilah penjelasan karakterisasi oleh simetri.]

Pertama, penjelasan demi contoh. Sebagai contoh, tentukan fungsi bantu . Jika adalah matriks permutasi, maka dan jika adalah diagonal, maka (produk dari entri diagonal). Sekarang, anggaplah adalah derajat homogen polinomial dalam variabel (yang kita anggap sebagai keinginan dari sebuah matriks ). Jika memiliki simetri berikut:A q ( A ) = 1 A q ( A ) = d e t ( A $q$$A$$q(A)=1$$A$$q(A)=det(A)$n n 2 n × n X $p(X)$$n$$n^2$$n \times n$$X$$p$

• $p(X) = p(X^t)$ (transpos)
• $p(AXB) = p(X)$ untuk semua pasangan matriks sehingga dan masing-masing merupakan matriks permutasi atau matriks diagonal danA B q ( A ) q ( B ) = $(A,B)$$A$$B$$q(A)q(B) = 1$

maka merupakan kelipatan konstan untuk semua matriks . Karena itu kami katakan permanen ditandai dengan simetri.p e r m ( X ) $p(X)$$perm(X)$$X$

Secara lebih umum, jika kita memiliki polinomial (homogen) dalam variabel , maka (grup semua matriks dapat dibalik ) bekerja pada oleh untuk (di mana kita mengambil variabel sebagai dasar untuk ruang vektor -dimensi tempat bekerja secara alami). Stabilizer dalam adalah subkelompok . Kami katakanm G L m m × m f ( A f ) ( x 1 , . . . , x m ) = f ( A - 1 ( x 1 ) , . . . , A - 1 ( x m ) ) A ∈ $f(x_1, ..., x_m)$$m$$GL_m$$m \times m$$f$$(Af)(x_1,...,x_m) = f(A^{-1}(x_1),...,A^{-1}(x_{m}))$x 1 , . . . , x m m G L m f G L m$A \in GL_m$$x_1,...,x_m$$m$$GL_m$$f$$GL_m$f f ′ m $\text{Stab}(f) = \{ A \in GL_m : Af = f\}$$f$dicirikan oleh simetri jika yang berikut ini berlaku: untuk setiap polinomial homogen dalam variabel dengan derajat yang sama dengan , jika untuk semua , maka adalah kelipatan konstan .$f'$$m$$f$ A ∈ Stab ( f ) f ′$Af' = f'$$A \in \text{Stab}(f)$$f'$$f$

Jawaban Joshua Grochow adalah jawaban yang bagus, tetapi saya pikir layak untuk memberikan komentar yang lebih umum. Hasil Razborov-Rudich mengatakan bahwa jika Anda ingin membuktikan bahwa beberapa fungsi Boolean tidak ada dalam , maka (dengan asumsi Anda percaya hipotesis kriptografi mereka), Anda harus menggunakan beberapa properti dari fungsi itu yang entah tidak penting untuk dihitung atau dibagikan oleh hanya sejumlah kecil fungsi Boolean lainnya. Dalam praktiknya, tidak mudah menghasilkan properti yang cocok; Namun, pengamatan Razborov-Rudich sebenarnya tidak mengesampingkan sangat banyak rencana umum serangan terhadap batas bawah sirkuit, dengan tidak adanya rincian konkret tentang bukti yang dimaksudkan. Sebagai contoh, misalkan saya secara naif mengatakan bahwa rencana saya untuk membuktikanN P ⊈ P / p o l y S A T ∉ P / p o l y S A T N P N $P/poly$$NP\not\subseteq P/poly$terlibat menunjukkan bahwa , dan bahwa saya bermaksud menggunakan fakta bahwa adalah -complete. "Rencana serangan" naif ini hampir bebas-konten, tetapi Razborov – Rudich tidak mengesampingkannya, karena bukan properti besar.$SAT\notin P/poly$$SAT$$NP$$NP$

Dengan kata lain, Razborov – Rudich biasanya tidak menghadirkan banyak kendala pada tahap awal perencanaan garis serangan pada batas bawah sirkuit, selama Anda meninggalkan beberapa ruang dalam rencana Anda untuk akhirnya menggunakan "properti khusus" fungsi calon Boolean Anda. Hanya ketika Anda menyingsingkan lengan baju Anda dan mencoba untuk mengisi rincian argumen bahwa penghalang naturalisasi akan mulai memundurkan kepalanya dengan sungguh-sungguh. Mengingat bahwa GCT masih pada tahap awal pengembangan, kita seharusnya tidak perlu khawatir tentang naturalisasi (walaupun tentu saja perlu memeriksa bahwa program GCT tidak ditakdirkan untuk alasan sepele).

Anda mungkin juga ingin memeriksa eksposisi GCT Ken Regan , yang mencakup beberapa komentar tentang penghalang naturalisasi.