Konstruktivitas dalam Bukti Alam dan Kompleksitas Geometris

Baru-baru ini, Ryan Willams membuktikan bahwa Konstruktivitas dalam Bukti Alami tidak dapat dihindari untuk memperoleh pemisahan kelas kompleksitas: dan T C 0 . $\mathsf{NEXP}$$\mathsf{TC}^{0}$

Constructivity di Bukti Alam adalah suatu kondisi bahwa semua bukti kombinatorial di memenuhi kompleksitas rangkaian dan bahwa kita dapat memutuskan apakah fungsi target di (atau yang lain "keras" kelas kompleksitas) memiliki "keras" properti dengan algoritma yang berjalan di poli-waktu dalam panjang tabel kebenaran fungsi target.$\mathsf{NEXP}$

Dua kondisi lain: kondisi berguna yang membutuhkan "keras" properti tidak dapat dihitung dengan sirkuit di dan kondisi kebesaran bahwa properti keras adalah mudah untuk menemukan.$\mathsf{TC}^0$

Pertanyaanku adalah :

Apakah hasil ini membuat Teori Kompleksitas Geometrik (GCT) tidak tersedia untuk menyelesaikan masalah pemisahan utama seperti vs N P , P vs N C , atau N E X P vs T C 0 ?$\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NC}$$\mathsf{NEXP}$$\mathsf{TC}^0$

Referensi:

• Ryan Williams, " Bukti Alami Versus Derandomisasi "

Tidak, konstruktifitas yang tidak dapat dihindari pasti masih membuat GCT terbuka sebagai rencana serangan yang layak pada masalah-masalah batas bawah seperti vs P / p o l y .$NP$$P/poly$

$\{M_1, \dotsc, M_{p(n)}\}$

Kedua, sentralitas karakterisasi simetri (disebutkan sudah oleh siuman) dalam GCT telah menjadi lebih jelas sejak survei Regan. Jika karakterisasi simetri ternyata menjadi sangat penting bagi GCT seperti kelihatannya akan terjadi, maka ini sudah mengatasi kondisi umum. Untuk definisi karakterisasi simetri, lihat jawaban ini untuk pertanyaan sebelumnya yang berkaitan erat .

Untuk bukti bahwa karakterisasi simetri melanggar ukuran, lihat Bagian 3.4.3 "Karakterisasi simetri menghindari penghalang Razborov-Rudich" dalam tesis saya (colokan sendiri yang tidak tahu malu, tetapi saya tidak tahu di mana pun di mana ini ditulis sedemikian lengkapnya) . Saya menduga itu juga melanggar konstruktif, tetapi meninggalkannya sebagai pertanyaan terbuka di sana. (Sebelumnya pada Bab 3 ada juga gambaran teorema flip dalam GCT dan bagaimana mereka berhubungan dengan simetri-karakterisasi.)

(Saya merasa menarik bahwa karakterisasi simetri - properti yang kami curigai akan digunakan dalam GCT yang ada di sekitar Razborov - Rudich - digunakan untuk membuktikan teorema balik, yang pada dasarnya mengatakan bahwa konstruktif diperlukan.)

$NP$$P/poly$

$NEXP \not\subset TC^0$$NEXP \cap coNEXP \not\subset ACC$

$P$$NP$

Beberapa komentar lagi tentang ini: hubungan antara GCT dan Bukti Alami telah dibahas di masa lalu (bahkan dalam makalah GCT asli sendiri). Walaupun tampaknya tidak ada konsensus tentang "konstruktifitas" atau "kebesaran" mana yang akan dilanggar oleh pendekatan GCT, Mulmuley dan Sohoni berargumen pada satu titik bahwa jika GCT dapat dilaksanakan maka ia harus melanggar keagungan. Untuk referensi yang relevan, lihat Bagian 6 dari tinjauan umum Regan tentang GCT . Namun, saya harus menambahkan bahwa ikhtisar ini sudah berusia 10 tahun, dan sejumlah besar pekerjaan telah masuk ke GCT sejak saat itu; Saya tidak yakin apakah ada revisi / pendapat baru tentang ini. (Mungkin Josh Grochow bisa berpadu?)

Jawaban singkatnya adalah Tidak .

Pendekatan Teori Kompleksitas Geometrik menargetkan properti tertentu yang sangat langka, yang menurut Mulmuley tidak "besar" seperti yang didefinisikan oleh Razborov dan Rudich. Untuk argumen formal, lihat juga tesis Joshua Grochow , Bagian 3.4.3. Karakterisasi simetri menghindari penghalang Razborov-Rudich , dan jawabannya .

Paragraf berikut berasal dari On P vs. NP dan Teori Kompleksitas Geometris oleh Ketan Mulmuley ( JACM 2011 atau manuskrip ), Bagian 4.3 Rencana Tingkat Tinggi :

Tujuannya adalah untuk melakukan langkah-langkah ini secara eksplisit, mengeksploitasi karakterisasi oleh simetri permanen dan penentu. Kami akan menentukan apa artinya eksplisit nanti; lih. Hipotesis 4.6. Pendekatan ini sangat kaku dalam arti bahwa itu hanya bekerja untuk fungsi-fungsi keras yang sangat langka yang ditandai oleh simetri mereka. Kekakuan ekstrem ini jauh lebih dari apa yang dibutuhkan untuk melewati penghalang pembuktian alami [Razborov dan Rudich 1997].

Karena kedua kondisi konstruktif dan luas diperlukan untuk bukti alami (di mana kegunaannya implisit), membuktikan bahwa konstruktifitas tidak dapat dihindarkan tidak cukup untuk mengesampingkan pendekatan semacam itu (meskipun langkah besar ke depan).