Teknik-teknik canggih untuk menentukan kompleksitas batas bawah

Beberapa dari Anda mungkin telah mengikuti pertanyaan ini , yang ditutup karena tidak menjadi level penelitian. Jadi, saya mengekstraksi bagian pertanyaan yang ada di tingkat penelitian.

Di luar teknik "sederhana", seperti mengurangi menjadi penyortiran atau masalah lengkap EXPTIME, teknik apa yang telah digunakan untuk membuktikan batas bawah untuk kompleksitas waktu masalah?

Khususnya:

• Apa teknik "mutakhir" yang telah dikembangkan dalam dekade terakhir?
• Dapatkah teknik dari Aljabar Abstrak, Teori Kategori, atau cabang-cabang lain dari matematika "murni" yang khas diterapkan? (Misalnya, saya sering mendengar penyebutan "struktur aljabar" penyortiran, tanpa penjelasan nyata tentang apa artinya ini.)
• Apa hasil yang signifikan tetapi kurang diketahui untuk kompleksitas batas bawah?

Batas bawah untuk sirkuit aljabar

Dalam pengaturan sirkuit aljabar, di mana batas bawah pada ukuran rangkaian dianalogikan dengan batas bawah pada waktu, banyak hasil diketahui, tetapi hanya ada beberapa teknik inti dalam hasil yang lebih modern. Saya tahu Anda meminta batas bawah waktu, tetapi saya pikir dalam banyak kasus harapannya adalah bahwa batas bawah aljabar suatu hari akan mengarah ke mesin batas bawah Boolean / Turing. Hasil ini sering menggunakan teknik yang lebih dalam dari "matematika murni" seperti yang Anda katakan.

I. Tingkat terikat.

Strassen menunjukkan bahwa log derajat variasi aljabar tertentu yang terkait dengan fungsi (himpunan) adalah batas bawah pada ukuran rangkaian aljabar menghitung fungsi-fungsi tersebut.

II Komponen yang terhubung (atau lebih umum dimensi kelompok homologi yang lebih tinggi).

Ben-Or menunjukkan bahwa ukuran pohon keputusan aljabar nyata yang menentukan keanggotaan dalam set (semi-aljabar) setidaknya mana C adalah jumlah komponen yang terhubung dari set itu. Ben-Atau menggunakan ini untuk membuktikan Ω ( n log n ) batas bawah pada penyortiran (baik, elemen perbedaan, tetapi elemen perbedaan mengurangi untuk menyortir) dalam model pohon keputusan aljabar nyata. Yao memperluas ini dari komponen yang terhubung ke jumlah angka Betti dan membuktikan batas bawah yang optimal untuk masalah lain (seperti k- setara)). Dalam makalah yang berbeda Yao memperluas ini ke pohon keputusan aljabar atas bilangan bulat.$\log C$$C$$\Omega(n \log n)$$k$

AKU AKU AKU. Derivatif parsial.

Ini telah menjadi pekerja keras dari banyak sirkuit aljabar modern batas bawah. Saya percaya turunan parsial pertama kali digunakan untuk membuktikan batas bawah oleh Baur-Strassen, di mana mereka menunjukkan bahwa menghitung semua parsial pertama dari dapat dilakukan dalam ukuran 5 s di mana s adalah ukuran yang diperlukan untuk menghitung f . Dikombinasikan dengan batas derajat Strassen, ini memberi Ω ( n log n ) ukuran batas bawah pada berbagai fungsi, yang masih merupakan batas bawah terkuat pada ukuran sirkuit aritmatika tak terbatas untuk fungsi eksplisit.$f$$5s$$s$$f$$\Omega(n \log n)$

Penggunaan turunan parsial yang lebih baru tampaknya berasal dari sebuah makalah Nisan di mana ia membuktikan batas bawah pada sirkuit nonkomutatif dengan mempertimbangkan dimensi ruang semua turunan parsial. Ini digunakan untuk membuktikan batas bawah pada jenis sirkuit kedalaman-3 terbatas oleh Nisan-Wigderson, dan ide serupa digunakan untuk membuktikan batas bawah pada ukuran rumus multilinear oleh Raz (dan model terkait oleh Raz dan kolaborator). Batasan terbaru 4 dan kedalaman 3 batas bawah oleh Gupta, Kayal, Kamath, dan Saptharishi menggunakan generalisasi dari gagasan ini, untuk menghitung dimensi ruang "turunan bergeser parsial" - di mana Anda dapat mengambil turunan parsial dan kemudian mengalikannya dengan setiap monomial dengan tingkat tertentu. ) dapat "hanya" menjadi masalah untuk mendapatkan pemahaman yang lebih baik dari ideal yang dihasilkan oleh anak di bawah umur permanen (lihat dugaan di akhir makalah mereka).$\mathrm{VP} \neq \mathrm{VNP}$

IV. Menentukan persamaan untuk varietas.

Idenya di sini adalah untuk mengasosiasikan ke "fungsi yang mudah" suatu varietas aljabar tertentu, menemukan persamaan yang menghilang pada varietas ini, dan menunjukkan bahwa persamaan ini tidak hilang pada "fungsi keras" Anda. (Karenanya membuktikan bahwa fungsi keras Anda tidak dalam berbagai fungsi mudah, sehingga sebenarnya sulit.) Terutama berguna dalam batas bawah pada perkalian matriks. Lihat Landsberg - Ottaviani di arXiv untuk yang terbaru, dan referensi ke batas bawah sebelumnya.

(Faktanya, I, II, dan III di atas semuanya dapat dipandang sebagai kasus khusus dalam menemukan persamaan untuk varietas tertentu, meskipun bukti yang menggunakan I, II, III pada dasarnya tidak pernah diutarakan seperti itu, karena sebenarnya tidak ada perlu.)

V. Teori Representasi, khususnya. seperti dalam teori kompleksitas geometris.

Sebenarnya, juga digunakan oleh Landsberg - Ottaviani untuk menemukan beberapa persamaan untuk varietas tertentu. Juga digunakan oleh Burgisser-Ikenmeyer untuk mendapatkan bukti "murni" representasi-teori dari batas bawah yang sedikit lebih lemah pada perkalian matriks. Dugaan oleh Mulmuley dan Sohoni (lih. "Teori Kompleksitas Geometris I & II") berguna untuk menyelesaikan vs V N P dan pada akhirnya N P vs P / p o l y .$\mathrm{VP}$$\mathrm{VNP}$$\mathrm{NP}$$\mathrm{P/poly}$

Kaveh dengan lembut menyarankan dalam jawabannya bahwa saya harus mengatakan sesuatu. Saya tidak punya banyak hal lain untuk disumbangkan pada daftar jawaban yang lengkap dan bagus ini. Saya dapat menambahkan beberapa kata umum tentang bagaimana "kompleksitas struktural" batas bawah telah berevolusi selama sepuluh tahun terakhir. (Saya menggunakan nama "kompleksitas struktural" hanya untuk membedakan dari aljabar, kompleksitas komunikasi, dll.)

Pendekatan saat ini sebagian besar masih didasarkan pada diagonalisasi, dan khususnya paradigma dasar berikut: Mulailah dengan mengasumsikan kebalikan dari batas bawah. Ini memberi Anda algoritma yang bagus untuk beberapa masalah. Coba gunakan algoritme itu untuk bertentangan dengan beberapa teorema hierarki yang didasarkan pada diagonalisasi, seperti hierarki waktu atau hierarki ruang. Karena argumen diagonalisasi saja tidak cukup untuk membuktikan batas bawah yang baru, bahan-bahan lain ditambahkan ke dalam campuran untuk mendapatkan resep kontradiktif.

Saya harus mengatakan bahwa banyak argumen dari tahun 70-an dan 80-an juga dapat dikatakan mengikuti pola di atas; perbedaan utama saat ini adalah "bahan lain" - ada banyak bahan untuk dipilih, dan cara-cara di mana bahan dapat diterapkan tampaknya hanya dibatasi oleh kreativitas Anda sendiri. Terkadang, ketika Anda tidak tahu cara mencampur bahan-bahan tertentu untuk mendapatkan resep yang lebih baik, tetapi Anda sangat memahami bagaimana mereka bisa mencampur, itu membantu untuk membuat kode program komputer yang menyarankan resep baru untuk Anda.

$NEXP \not\subset ACC$

Teknik-teknik tergantung pada model dan jenis sumber daya yang kita inginkan. Perhatikan bahwa untuk membuktikan batas bawah pada kompleksitas masalah, pertama-tama kita harus memperbaiki model matematika perhitungan: batas bawah untuk status masalah adalah bahwa tidak ada algoritma yang menggunakan sejumlah sumber daya yang dapat memecahkan masalah, yaitu kita menghitung secara universal lebih dari algoritma. Kita perlu memiliki definisi matematis dari domain kuantifikasi. (Ini umumnya berlaku untuk hasil ketidakmungkinan.) Oleh karena itu, hasil batas bawah hanya berlaku untuk model perhitungan tertentu. Misalnya,$\Omega(n \log n)$batas bawah untuk penyortiran hanya berfungsi untuk algoritma penyortiran berbasis perbandingan, tanpa batasan ini dan dalam model komputasi yang lebih umum, mungkin untuk menyelesaikan penyortiran lebih cepat, bahkan waktu linear. (Lihat komentar Josh di bawah ini.)

Berikut adalah beberapa metode dasar langsung untuk membuktikan batas bawah dalam teori kompleksitas komputasi untuk model komputasi yang lebih umum (mesin dan sirkuit Turing).

I. Menghitung:

Ide: Kami menunjukkan bahwa ada lebih banyak fungsi yang algoritme.

Mis: Ada fungsi yang membutuhkan sirkuit besar secara eksponensial.

Masalah dengan metode ini adalah bahwa itu adalah argumen eksistensial dan tidak memberikan fungsi eksplisit atau batas atas pada kompleksitas masalah yang terbukti sulit.

II Kombinatorial / Aljabar:

Ide: Kami menganalisis sirkuit dan menunjukkan bahwa mereka memiliki properti tertentu, misalnya fungsi yang dikomputasi oleh mereka dapat didekati oleh beberapa kelas objek matematika yang bagus, sedangkan fungsi target tidak memiliki properti itu.

Mis: Lemma pengalihan Håstad dan variannya menggunakan pohon keputusan untuk memperkirakan , Razborov-Smolensky menggunakan polinomial pada bidang untuk memperkirakan fungsi , dll. A C 0 [ p $\mathsf{AC^0}$$\mathsf{AC^0}[p]$

Masalah dengan metode ini adalah bahwa dalam praktiknya hanya bekerja untuk kelas kecil dan relatif mudah untuk dianalisis. Ada juga penghalang Bukti Alami dari Razborov-Rudich yang dengan cara memformalisasikan mengapa sifat-sifat sederhana sendiri tidak mungkin cukup untuk membuktikan batas bawah sirkuit yang lebih umum.

Makalah Razborov " Pada metode aproksimasi " berpendapat bahwa metode aproksimasi lengkap untuk membuktikan batas bawah dalam arti tertentu.

AKU AKU AKU. Diagonalisasi:

Ide. Kami mendiagonalisasi terhadap fungsi di kelas yang lebih kecil. Idenya kembali ke Gödel (dan bahkan Cantor).

Ex. Teorema hierarki waktu , teorema hierarki ruang , dll.

$\mathsf{P}$$\mathsf{PSpace}$$\mathsf{P}$$\mathsf{PSpace}$

Kami juga memiliki penghalang relativization (kembali ke Baker, Gill, dan Solovay) dan penghalang aljabar (oleh Aaronson dan Wigderson) yang menyatakan bahwa jenis argumen diagonalisasi tertentu akan ditransfer ke pengaturan lain di mana hasilnya terbukti salah.

Perhatikan bahwa hambatan ini tidak berlaku untuk argumen diagonalisasi yang lebih umum. Bahkan, oleh makalah Dexter Kozen " Pengindeksan kelas subkursif ", diagonalisasi lengkap untuk membuktikan batas bawah.

Seperti yang mungkin telah Anda perhatikan, ada hubungan yang kuat antara menemukan simulator universal yang bagus untuk kelas kompleksitas dan memisahkan kelas kompleksitas dari kelas yang lebih besar (untuk pernyataan formal lihat makalah Kozen).

Karya terbaru

Untuk kemajuan terbaru, periksa makalah terbaru Ryan Williams . Saya tidak membahasnya dalam jawaban ini karena saya berharap Ryan sendiri akan menulis jawaban.

Pohon keputusan aljabar

Ini bukan teknik baru, tetapi teknik yang cukup kuat untuk masalah tertentu.

$n$$d$

• $v$$q_v(x_1, \dots, x_n)$$d$$x_i-x_j$$i$$j$

• $-1$$0$$+1$

• $\{1,2,\dots,n\}$

$\vec{x}\in\mathbb{R}^n$

$\Omega(n^d)$

$\ell$$R(\ell) \subseteq \mathbb{R}^n$$\ell$$R(\ell)$$\mathbb{R}^n$$t = \text{depth}(\ell)$$d$$d$$(dt)^{O(n)}$

$W\subseteq\mathbb{R}^n$$d$$t$$W$$3^t (dt)^{O(n)}$$t = \Omega(\log \#W - n\log d)$

$n$$W$$n!$$n$$\Omega(n\log n)$

$\Omega(n\log n)$

$R(\ell)$$(dt)^{O(n)}$

$n^{O(n)}$$n\log n$

$\Omega(n^2)$$O(n^4\log n)$$2^{O(n)}$$\mathbb{R}^n$$n^4\log n$$k$$k$$k$$k$$O(n^{k/2})$$O(n^4\log n)$polinomial kueri; waktu konstruksi ini gratis dalam model batas bawah.

Hore untuk hasil ganda negatif!

Manindra Agrawal memiliki makalah yang bagus "Membuktikan Batas Bawah via Generator Psuedorandom". Ini mungkin dianggap sebagai "kuda hitam" dalam menjalankan untuk membuktikan batas bawah tetapi makalah ini menarik.

ini adalah survei 32p yang baru saja muncul pada subjek yang berfokus pada sirkuit batas bawah sudut (ada tumpang tindih yang kuat dalam konten dengan jawaban lain di sini).

• Algoritma versus Sirkuit Batas Bawah oleh Oliveira

Teknik yang berbeda telah digunakan untuk membuktikan beberapa teorema transferensi dari bentuk "algoritma nontrivial untuk kelas sirkuit C menghasilkan rangkaian batas yang lebih rendah terhadap C". Dalam survei ini kami meninjau kembali banyak hasil ini. Kami membahas bagaimana rangkaian batas bawah dapat diperoleh dari derandomisasi, kompresi, pembelajaran, dan algoritme kepuasan. Kami juga membahas hubungan antara batas bawah sirkuit dan sifat yang berguna, gagasan yang ternyata mendasar dalam konteks teorema pemindahan ini. Sepanjang jalan, kami memperoleh beberapa hasil baru, menyederhanakan beberapa bukti, dan menunjukkan koneksi yang melibatkan kerangka kerja yang berbeda. Kami berharap bahwa presentasi kami akan berfungsi sebagai pengantar mandiri bagi mereka yang tertarik dalam mengejar penelitian di bidang ini.