Aplikasi kompleksitas Kolmogorov dalam kompleksitas komputasi

Secara informal, kompleksitas Kolmogorov dari string adalah panjang dari program terpendek yang menghasilkan x . Kita dapat mendefinisikan gagasan 'string acak' yang menggunakannya ( x adalah acak jika K ( x ) ≥ 0,99 | x | ) Mudah untuk melihat bahwa sebagian besar string adalah acak (tidak ada begitu banyak program pendek).$x$$x$$x$$K(x) \geq 0.99 |x|$

Teori kompleksitas Kolmogorov dan teori informasi algoritmik cukup berkembang saat ini. Dan ada beberapa contoh lucu menggunakan kompleksitas Kolmogorov dalam bukti teorema yang berbeda yang tidak mengandung apa pun tentang kompleksitas Kolmogorov dalam pernyataan mereka ( LLL konstruktif , ketimpangan Loomis-Whitney dan sebagainya).

Apakah ada aplikasi bagus dari kompleksitas Kolmogorov dan teori informasi algoritmik dalam kompleksitas komputasi dan bidang terkait ? Saya merasa bahwa harus ada hasil yang menggunakan kompleksitas Kolmogorov sebagai pengganti langsung dari penghitungan argumen sederhana. Ini tentu saja tidak begitu menarik.

Lance Fortnow telah menulis artikel tentang topik ini: Kompleksitas Kolmogorov dan Kompleksitas Komputasi

Anda juga harus memeriksa Pengantar Kompleksitas Kolmogorov dan Penerapannya oleh Li dan Vitanyi, buku definitif tentang masalah ini. Secara khusus, bab 6 "Metode Tidak Dapat Dikompresi" membahas sejumlah aplikasi dalam kompleksitas seperti bukti kompleksitas Kolmogorov dari lemma switching Hastad (dari Circuit Lower Bounds à la Kolmogorov oleh Fortnow dan Laplante).

Dan ada aplikasi dalam kompleksitas komunikasi (misalnya Kompleksitas Kolmogorov dan Metode Kombinasi dalam Kompleksitas Komunikasi oleh Kaplan dan Laplante).

Hanya beberapa hari yang lalu Scott Aaronson menggunakan argumen berdasarkan kompleksitas Kolmogorov untuk menunjukkan Kesetaraan Sampling dan Pencarian . Lebih lanjut ia berpendapat, bahwa dalam argumennya kompleksitas Kolmogorov digunakan dalam cara yang penting, itu bukan hanya jalan pintas untuk argumen penghitungan.

Hasil ini oleh Alon et al. dapat diperoleh dengan menggunakan kompleksitas Kolmogorov.

$\mathrm{poly}(\log |E|)$

Satu kertas bagus yang saya ketahui (selain kertas bagus lainnya yang disebutkan dalam jawaban lain):

Juris Hartmanis, Kompleksitas Kolmogorov Umum dan Struktur Komputasi yang Layak , FOCS 1983.

Hal utama yang saya ingat dari makalah itu adalah konstruksi berbasis kompleksitas Kolmogorov dari oracle yang memisahkan P dari NP.

Makalah lain yang terlintas dalam pikiran adalah

Allender et al., Kekuatan dari Random Strings , FOCS 2002 ( versi ECCC ) dan SICOMP 2006 .

Jika saya ingat, makalah ini memisahkan kelengkapan Turing polinomial-waktu dari kelengkapan banyak-satu log-ruang di PSPACE, menggunakan argumen kompleksitas Kolmogorov. Tentu saja, ia melakukan banyak hal lain, tetapi saya ingat pemisahan itu menjadi satu aplikasi yang merupakan kepentingan independen di luar teori informasi algoritmik.

Ada juga teknik quantum lower bound yang menggunakan kompleksitas Kolmogorov:

" Batas bawah untuk kompleksitas kueri acak dan kuantum menggunakan argumen Kolmogorov " oleh Sophie Laplante dan Frederic Magniez

$s$$K(s)$

(Sekarang untuk bagian yang serius.) Daniil Musatov baru-baru ini menunjukkan bahwa derandomisasi naif dapat memberikan konstruksi yang masuk akal untuk objek yang biasanya terbukti ada secara non-konstruktif melalui metode probabilistik. Saya pikir ini mungkin untuk menyediakan aplikasi masa depan yang signifikan dari kompleksitas Kolmogorov yang terbatas sumber daya untuk kompleksitas komputasi.

• Daniil Musatov, Memperbaiki Versi Bounded Version dari Teorema Complexity Bersyarat Muchnik melalui Derandomisasi `` Naif ' , CSR 2011, LNCS 6651, 64-76. doi: 10.1007 / 978-3-642-20712-9_6 ( pracetak )

Lihat juga makalah yang mengutip yang ini .

(Edit: menautkan ke versi yang lebih baru, yang diterbitkan.)

H. Buhrman, L. Fortnow, dan S. Laplante. Kompleksitas Kolmogorov yang terbatas sumber daya ditinjau kembali. SIAM Journal on Computing, 31 (3): 887-905, 2002. ( jurnal , halaman web Lance ).

Termasuk aplikasi kompleksitas Kolmogorov seperti:

• Sebuah bukti Valiant-Vazirani
• Penugasan yang memuaskan dari rumus Boolean dapat disebutkan dalam polinomial waktu dalam ukuran keluaran jika penugasan unik dapat ditemukan dengan cepat
• Bukti baru bahwa BPP ada di Sigma_2 P
• Beberapa konstruksi oracle

Beberapa di atas pertama kali terbukti dalam makalah ini, sedangkan yang lain hanyalah bukti baru dari teorema lama, menggunakan kompleksitas Kolmogorov.

Aplikasi kompleksitas Kolmogorov yang terikat waktu dalam teori kompleksitas adalah survei yang bagus oleh Eric Allender dari aplikasi lain. Meskipun banyak dari hasil di sini adalah implikasi, beberapa adalah aplikasi yang benar, seperti yang berikut:

• Kor 13: Sehubungan dengan oracle generik, tidak ada generator pseudorandom yang aman terhadap lawan P / poly.
• Thm 16 [Allender dan Gore, 1991]: Ada relatif oracle yang semua predikat NE dapat dipecahkan dalam waktu eksponensial dan E = Union_k \ Sigma_k-TIME (n).

Kedua bukti menggunakan kompleksitas Kolmogorov secara signifikan.

$D$$D$

Panjang Deskripsi Minimum menggunakan kompleksitas Kolmogorov (atau perkiraan dan generalisasi daripadanya, karena ketidakpastian) dalam pembelajaran informasi-teoretis dan teori inferensi. Secara khusus, MDL digunakan untuk menemukan penjelasan data yang secara alami menghindari overfitting.

Jorma Rissanen memberikan pengantar yang bagus untuk konsepnya: http://www.mdl-research.org/jorma.rissanen/pub/Intro.pdf

Maksud Anda sesuatu seperti ini, ilyaraz?

http://arxiv.org/abs/1004.3993