Nilai yang diharapkan dari kompleksitas Kolmogorov dalam sampel acak

Kompleksitas string Kolmogorov tidak dapat dihitung. Namun, dalam bagian acak ukuran dari string biner dengan panjang , berapa banyak yang diharapkan memiliki kompleksitas kurang dari beberapa bilangan bulat kurang dari (sebagai fungsi dari , dan )?$M$$n$$n_{0}$$n$$M$$n$$n_{0}$

Kompleksitas Kolmogorov hanya ditentukan hingga beberapa tetapan aditif, sehingga tidak mungkin untuk memberikan jawaban yang tepat. Batas yang saya jelaskan di sini bahkan lebih lemah.

Tentu saja angka yang diharapkan dapat dihitung dengan mudah setelah kita tahu berapa banyak string memiliki kompleksitas kurang dari , jadi izinkan saya menjawab ini. Biasanya pernyataan pertama tentang kompleksitas Kolmogorov bahwa angka ini paling banyak - karena hanya ada banyak string dengan panjang yang lebih kecil. Di sisi lain, jika program Anda mengatakan "panjang , ambil angka th", maka Anda mendapatkan string kompleksitas kurang dari , di mana adalah versi awalan-bebas dari kompleksitas Kolmogorov dari (jadi paling banyakn 0 2 n 0 - 1 n x 2 n 0 - K ( n ) - C n 0 K ( n ) n log n + log ∗ n + O ( 1 ) p x n x n O ( 1 ) p $2^n$$n_0$$2^{n_0}-1$$n$$x$$2^{n_0-K(n)-C}$$n_0$$K(n)$$n$$\log n+\log^* n + O(1)$). Secara lebih rinci, string pertama berisi deskripsi dari mesin Turing yang mengambil input , di mana p adalah deskripsi dari program bebas awalan yang menghasilkan , menghasilkan jumlah panjang ke- , yaitu bit , dan kemudian ini diikuti oleh .$px$$n$$x$$n$$O(1)$$px$

Mungkin dimungkinkan untuk meningkatkan batasan ini, tetapi saya ragu Anda bisa mendapatkan jawaban yang tepat.

Jawaban yang tepat dapat diberikan. Jumlah string panjang dengan kompleksitas (polos) paling banyak n 0 adalah 2 n 0 - K ( n 0 | n ) , hingga faktor konstan. Karenanya setiap proses yang secara acak memilih suatu himpunan bagian akan memiliki, dengan probabilitas yang masuk akal, 2 - K ( n 0 | n ) + O ( 1 ) fraksi string kompleksitas kurang dari n 0 . Untuk menunjukkan klaim kami, cukup untuk menunjukkan bahwa jumlah string dengan kompleksitas$n$$n_0$$2^{n_0 - K(n_0|n)}$$2^{-K(n_0|n) + O(1)}$$n_0$sama dengan juga diberikan oleh 2 k - K ( k | n ) . Kita dapat menunjukkan hasil yang diperlukan dengan menentukan penjumlahan dari nilai ini di atas k dari 1 hingga n 0 . Untuk menunjukkan ini, kami menggunakan hasil aditivitas untuk kompleksitas polos (karena B. Bauwens dan A. Shen. Teorema aditivitas untuk kompleksitas Kolmogorov polos . Teori Sistem Komputasi, 52 (2): 297-302, Feb 2013), C ( a , b ) = K ( a | C ( a , b $k$$2^{k - K(k|n)}$$k$$n_0$ Di sini K ( ⋅ ) menunjukkan kompleksitas Kolmogorov yang bebas awalan. Memilih a = n , kita amati bahwa untuk setiapstring n- bit b dari kompleksitas k kita memiliki k = C ( b ) = C ( n , b ) + O

$$C(a,b) = K(a|C(a,b)) + C(b|a,C(a,b)) + O(1).$$ $K(\cdot)$$a = n$$n$$b$$k$ Karenanya, untuk masing-masing b tersebut kita memiliki C ( b | n , k ) = k - K ( n | k ) + O ( 1 ) . Biarkan k ′ = k - K ( n $$k = C(b) = C(n,b) + O(1) = K(n|k) + C(b|n,k) + O(1).$$ $b$$C(b|n,k) = k - K(n|k)+O(1)$ . Sekarang kita dapat mengamati bahwa ada paling banyakstring O ( 2 k ′ ) b , dan masing-masing leksikografis pertama 2 k ′ string dengan panjang n memenuhi C ( b | n , k ) ≤ k ′ + O ( 1 ) . Jadi Ω ( 2 k ′ ) dari mereka memenuhi C ( b | n , k ) $k' = k - K(n|k)$$O(2^{k'})$$b$$2^{k'}$$n$$C(b|n,k) \le k' + O(1)$$\Omega(2^{k'})$ .$C(b|n,k) = k' + O(1)$