Varian kompleksitas Kolmogorov yang dapat dihitung secara efisien

Kompleksitas awalan Kolmogorov (yaitu adalah ukuran program pembatasan-diri minimal yang menghasilkan x ) memiliki beberapa fitur bagus:$K(x)$$x$

1. Ini sesuai dengan intuisi memberikan string dengan patters atau struktur kompleksitas yang lebih rendah daripada string tanpa.
2. Hal ini memungkinkan kita untuk mendefinisikan kondisional kompleksitas , atau bahkan lebih baik K ( x | O ) untuk beberapa oracle O .$K(x|y)$$K(x|O)$$O$
3. Ini adalah sub-aditif .$K(x,y) \leq K(x) + K(y)$

Namun ia memiliki kelemahan yang mengerikan: mengembalikan diberikan x tidak dapat ditentukan.$K(x)$$x$

Saya bertanya-tanya apakah ada varian kompleksitas Kolmogorov menggunakan model komputasi yang dibatasi (baik dengan menggunakan bahasa yang lebih lemah daripada TM, atau menggunakan TM yang didukung sumber daya) yang mempertahankan fitur (1) dan (2) (fitur ( 3) apakah bonus, tetapi bukan keharusan) sambil dihitung secara efisien?$K'(x)$

Motivasi untuk pertanyaan ini adalah untuk digunakan dalam studi simulasi berbagai model mainan evolusi. Jadi jawaban yang telah digunakan sebagai 'perkiraan kasar' untuk kompleksitas Kolmogorov dalam pekerjaan numerik sebelumnya lebih disukai. Namun, tujuannya bukan untuk sepenuhnya eksperimental, jadi bahasa / model-komputasi-komputasi yang relatif sederhana / bersih untuk lebih disukai, sehingga dimungkinkan untuk membuktikan beberapa teorema yang masuk akal tentang seberapa drastis K ′ berbeda dari K dan pada string apa.$K'$$K'$$K$

Menghubungkan pertanyaan

Kompleksitas Kolmogorov dengan bahasa deskripsi yang lemah

Apakah ada gagasan yang masuk akal tentang algoritma aproksimasi untuk masalah yang tidak dapat ditentukan?

Gzip. Cilibrasi dan Vitanyi memiliki artikel yang sangat bagus di mana mereka menggunakan gzip sebagai perkiraan kompleksitas Kolmogorov untuk melakukan pengelompokan. Clustering dengan Kompresi

Saya lebih memikirkan pertanyaan saya, dan tiba pada solusi yang mungkin. Ini memiliki dua keterbatasan, hanya didefinisikan pada string dengan panjang (meskipun saya akan membahas ini lebih lanjut) dan tidak berbicara tentang mesin Turing universal, alih-alih mengikuti pertanyaan sebelumnya dan menggunakan model komputasi alternatif.$n = 2^m$

Pada dasarnya, kita dapat menginterpretasikan string dengan | x | = 2 m sebagai fungsi f x : { 0 , 1 } m → { 0 , 1 } . Maka ukuran kompleksitas kami K ′ ( x ) adalah ukuran (jumlah tepi) dari diagram keputusan biner tereduksi unik (ROBDD; dengan pemesanan standar tetap) yang mewakili f x . Kondisi ini memuaskan [1]. Juga, karena ROBDD dapat dihitung dalam polinomial waktu dalam 2 $x$$|x| = 2^m$$f_x: \{0,1\}^m \rightarrow \{0,1\}$$K'(x)$$f_x$$2^m$, kami memiliki ukuran yang efisien.

Untuk memenuhi persyaratan [2], kita harus memodifikasi BDD standar dengan mengizinkan tipe khusus pada node. Biasanya node diberi label oleh indeks , kami akan menyertakan simpul oracle khusus. Untuk K ( x | y ) di mana | y | = 2 m kami akan mengizinkan node khusus dalam BDD sebagai berikut:$i \in \{1,...,m\}$$K(x|y)$$|y| = 2^m$

$a$$|a| = m$$i$$a_i$$f_y(a)$$K'(x|x) = 2$$K'(x|y) \approx K(x)$$y$

[Catatan: tidak jelas apakah kompleksitas bersyarat masih dapat dihitung secara efisien :(]

Secara konvensional, kami juga memiliki sub-aditivitas karena membangun OBDD untuk kita dapat memiliki kueri untuk bit pertama dan pada 0 pergi ke ROBDD untuk x dan pada 1 ke ROBDD untuk y . Jadi, kita memiliki K ′ ( x . Y ) ≤ K ′ ( x ) + K ′ ( y ) .$x.y$$0$$x$$1$$y$$K'(x.y) \leq K'(x) + K'(y)$

$K'(x)$$x$$|x| = 2^m$$|y| = 2^l$$m > l$$K'(x.y) = K'(x) + K'(y)$

Sayangnya ada juga beberapa batasan dengan pendekatan saya. Kami tidak bisa melangkah lebih jauh dari OBDD, jika kami mempertimbangkan pohon keputusan minimal atau hanya BDD maka kami akan mengambil masalah yang tidak bisa ditanggulangi yang dibahas dalam jawaban ini . Bahkan untuk pemesanan variabel dari OBDD tampaknya ada hasil yang tidak dapat dipraktikkan . Jadi sepertinya OBDD adalah batas dari pendekatan kompleksitas-Kolmogorov yang tidak begitu mirip dengan standar ini.

Saya bukan ahli, tetapi jika Anda membutuhkan ukuran kompleksitas praktis untuk string, Anda dapat melihat ke ukuran T-kompleksitas Titchener .

Lihat situs web Titchener untuk pengantar cepat; nya makalah dapat didownload dalam format pdf .

Abstrak - Ukuran baru kompleksitas string untuk string terbatas disajikan berdasarkan proses produksi string hierarki rekursif tertentu . Dari batas maksimal, kami menyimpulkan hubungan antara kompleksitas dan konten informasi total. Artikel lengkap ...

Saya menemukan beberapa makalah tentang implementasi praktis juga (lihat misalnya " Algoritma T-dekomposisi Cepat ")

Pada dasarnya, hampir semua mesin pembelajaran atau metode kompresi adalah perkiraan untuk kompleksitas Kolmogorov:

• $p(x)$$- \log p(x)$
• $n$$K(x) \leq n + s_C$$s_C$$x$

Dengan demikian, Anda bisa mencari pola dengan kompresor atau distribusi probabilitas dan semakin baik kompres data Anda, semakin baik batas atas Anda untuk K (x). Pastikan untuk menambahkan ukuran kompresor itu sendiri ke ukuran data yang dikompresi untuk mendapatkan perkiraan.

$K(x)$

$K(x)$$K$

Anda juga dapat menggunakan batas waktu untuk mendefinisikan kelas model Anda, yang mengarahkan Anda ke jawaban Suresh. Pada dasarnya, jika Anda berasumsi bahwa sumber data Anda memiliki kompleksitas waktu polinomial, dan Anda mencoba semua mesin polinomial Turing untuk mengompresnya, Anda dapat yakin bahwa Anda telah secara akurat memperkirakan kompleksitas Kolmogorov. Ini mungkin masih tidak praktis, tetapi untuk batas waktu yang lebih rendah, Anda mungkin dapat menghitung campuran Bayesian penuh, dari perkiraan yang baik untuk itu.

Untuk detail teknis, lihat makalah ini . Penafian: Saya salah satu penulis.

$K(x)$$K(x)$

Anda sedang mencari kompleksitas Kolmogorov terbatas sumber daya. Anda bisa mulai dengan makalah ini dan cabang keluar.