Metode polinomial untuk hasil kompleksitas

Metode polinomial , katakanlah Combinatorial Nullstellensatz dan Chevalley-Warning theorem adalah alat yang ampuh dalam kombinatorik aditif. Dengan merepresentasikan masalah dengan polinomial yang tepat, mereka dapat menjamin keberadaan solusi, atau jumlah solusi untuk polinomial. Mereka telah digunakan untuk memecahkan masalah seperti jumlah terbatas atau masalah jumlah nol , dan beberapa teorema di daerah ini dapat dibuktikan hanya dengan metode seperti itu.

Bagi saya cara non-konstruktif dari metode ini benar-benar luar biasa, dan saya ingin tahu tentang bagaimana kita dapat menerapkan metode ini untuk membuktikan setiap inklusi yang menarik dan pemisahan kelas kompleksitas (bahkan jika hasilnya dapat diselesaikan dengan metode lain).

Adakah hasil kompleksitas yang diketahui bahwa seseorang dapat membuktikannya dengan metode polinomial?

Beberapa contoh klasik dari penggunaan metode polinomial adalah:

• Bukti Razborov-Smolensky tentang "Parity not in " ( banyak eksposisi tersedia secara online, ini salah satunya )$AC^0$
• Bukti Beigel-Reingold-Spielman tentang "PP ditutup di bawah persimpangan"
• Hasil Bazzi untuk membodohi DNF , dan bukti Braverman tentang " Kemerdekaan Polylog membodohi $AC^0$ "

Juga, analisis fourier dari fungsi boolean (di sini adalah kursus yang hebat oleh Ryan O'Donnell ) memiliki koleksi besar hasil yang luar biasa, favorit saya adalah bukti Kushilevitz-Mansour-Nisan tentang teorema Goldreich-Levin .

Scott Aaronson sebenarnya telah memberikan tutorial di FOCS'08 tentang " Metode Polinomial dalam Komputasi Klasik dan Kuantum (ppt) ".

Semoga ini membantu.

Ada hasil Zeev Dvir pada masalah bidang terbatas Kakeya yang disebutkan di situs web ini sebelumnya. Zeev menggunakan metode polinomial untuk membatasi jumlah titik dalam setiap himpunan titik dalam F ^ n (bidang hingga F, n bilangan alami) yang berisi garis di setiap arah. Hasil ini sebenarnya menarik perhatian orang dalam analisis terhadap metode polinomial.

Hasil Zeev dimotivasi oleh tugas membangun ekstraktor acak . Ini adalah bagian dari upaya besar dalam ilmu komputer teoretis untuk derandomisasi algoritma, dan akhirnya menunjukkan bahwa P = BPP dan hasil kompleksitas yang sama berlaku.

Lihat lebih banyak dalam survei Zeev: http://www.math.ias.edu/~dvir/papers/Dvir09b.pdf