Program GCT Mulmuley

38

Kadang-kadang diklaim bahwa Teori Kompleksitas Geometri Ketan Mulmuley adalah satu-satunya program yang masuk akal untuk menyelesaikan pertanyaan terbuka teori kompleksitas seperti pertanyaan P vs NP. Ada beberapa komentar positif dari ahli teori kompleksitas terkenal tentang program ini. Menurut Mulmuley akan butuh waktu lama untuk mencapai hasil yang diinginkan. Memasuki daerah itu tidak mudah untuk teori kompleksitas umum dan membutuhkan upaya yang cukup untuk mendapatkan pegangan pada geometri aljabar dan teori representasi.

  1. Mengapa GCT dianggap mampu menyelesaikan P vs NP? Apa nilai klaim itu jika diperkirakan akan membutuhkan waktu lebih dari 100 tahun untuk sampai ke sana? Apa keuntungannya untuk pendekatan lain saat ini dan yang mungkin meningkat dalam 100 tahun ke depan?

  2. Bagaimana keadaan program saat ini?

  3. Apa target program selanjutnya?

  4. Apakah ada kritik mendasar terhadap program ini?

Saya lebih suka jawaban yang dapat dimengerti oleh teori kompleksitas umum dengan latar belakang minimum dari geometri aljabar dan teori representasi yang diasumsikan.

cc.complexity-theory big-picture algebraic-complexity p-vs-np gct Anonim
sumber
12
Apakah Anda melihat tutorial Mulmuley di FOCS (tersedia di techtalks.tv/talks/1301 ) dan sudahkah Anda membaca paparan Ken Regan: theorie.informatik.uni-ulm.de/Personen/toran/beatcs/… ? Mulmuley benar-benar memberikan intuisinya mengapa menurutnya programnya bisa berjalan (dan saya pikir dia berpendapat bahwa itu bahkan perlu), dan juga mengapa itu sulit.
Sasho Nikolov
5
Posting blog terkait: 1 , 2 . Scott juga menulis: "Program GCT Mulmuley adalah satu-satunya pendekatan untuk P vs NP yang pernah saya lihat yang bahkan memiliki aspirasi serius untuk" tahu tentang "banyak teknik nontrivial untuk memecahkan masalah dalam P (setidaknya, pencocokan dan pemrograman linier) Bagi saya, itu mungkin satu-satunya argumen terkuat yang mendukung GCT. "
Kaveh
7
Saya pikir GCT bertujuan VP vs VNP dan bukan P vs NP.
Iddo Tzameret
6
@Iddo: Sebenarnya itu bisa ditujukan pada banyak hal (lebih dari yang saat ini ditujukan). Untuk "perm v det lebih " itu bertujuan ¯ V P w s vs V N P (lihat arxiv.org/abs/0907.2850 ). Namun, lebih dari bidang terbatas dan untuk fungsi selain perm dan det, itu dapat diarahkan langsung ke P vs NP. CVPws¯VNP
Joshua Grochow
4
@Mohammad: Hanya karena sebuah solusi akan tidak terduga dan membutuhkan ide-ide baru sepenuhnya tidak berarti bahwa itu bukanlah solusi yang akan berjalan. Memang, banyak yang sudah percaya bahwa menyelesaikan P vs NP dengan metode apa pun akan membutuhkan gagasan yang sepenuhnya baru ...
Joshua Grochow

Jawaban:

23

Seperti yang ditunjukkan oleh banyak orang lain, banyak yang telah dikatakan pada banyak pertanyaan ini oleh Mulmuley, Regan, dan lainnya. Saya akan menawarkan di sini hanya ringkasan singkat dari apa yang saya pikir adalah beberapa poin kunci yang belum disebutkan dalam komentar.

  1. Mengenai mengapa GCT dianggap masuk akal mampu menunjukkan banyak jawaban telah diberikan di tempat lain dan dalam komentar di atas, meskipun saya pikir belum ada yang menyebutkan bahwa itu tampaknya untuk menghindari hambatan yang diketahui (relativization, algebrization, bukti alami ). Mengenai nilainya - saya pikir bahkan jika itu membutuhkan kita 100 tahun, kita akan belajar sesuatu yang baru tentang kompleksitas di sepanjang jalan dengan mempelajarinya dari sudut ini.P≠NP

    • Beberapa kemajuan sedang dibuat pada pemahaman varietas aljabar, representasi, dan pertanyaan algoritmik yang muncul dalam GCT. Peneliti utama yang saya tahu yang telah melakukan pekerjaan ini adalah (tanpa urutan tertentu): P. Burgisser, C. Ikenmeyer, M. Christandl, JM Landsberg, KV Subrahmanyan, J. Blasiak, L. Manivel, N. Ressayre, J. Weyman, V. Popov, N. Kayal, S. Kumar, dan tentu saja K. Mulmuley dan M. Sohoni.

    • Lebih konkret, Burgisser dan Ikenmeyer baru saja menyajikan (STOC 2011) beberapa batas bawah sederhana pada perkalian matriks menggunakan pendekatan GCT ( , dibandingkan dengan yang saat ini paling dikenal 3n2+232n2+HAI(n)

    • N. Kayal memiliki beberapa makalah tentang pertanyaan algoritmik pengujian ketika satu polinomial berada di orbit yang lain atau merupakan proyeksi yang lain. Dia menunjukkan bahwa secara umum masalah-masalah ini NP-keras tetapi untuk fungsi-fungsi khusus seperti polinomial simetris permanen, determinan, dan dasar, masalah-masalah ini dapat dipecahkan dalam P. Ini adalah langkah menuju beberapa dugaan Mulmuley (bahwa masalah-masalah sulit tertentu - menentukan orbit Penutupan - berada di P untuk fungsi khusus seperti penentu).

  3. Saya tidak memiliki jauh lebih spesifik untuk mengatakan ini daripada jawaban 2.

  4. Sejauh yang saya tahu belum ada kritik mendasar , dalam arti bahwa saya belum melihat ada kritik yang benar-benar mendiskreditkan program dengan cara apa pun. Sudah pasti ada diskusi tentang mengapa teknik seperti itu perlu, nilai program mengingat horizon waktu yang lama, dll., Tetapi saya akan menganggap ini lebih sebagai diskusi yang sehat daripada kritik mendasar.

Joshua Grochow
sumber
1
@ user124864: Pada prinsipnya ya. GCT hanyalah sebuah pendekatan untuk menunjukkan batas bawah, apa pun batas bawah itu. Sepertinya itu harus bekerja lebih baik untuk fungsi yang ditandai oleh simetri mereka, tetapi properti yang terakhir tidak tergantung pada nilai numerik dari batas bawah yang ingin Anda tampilkan (misalnya quasipoly vs exp).
Joshua Grochow