Apakah ada x sedemikian rupa sehingga K (xx) <K (x), di mana K adalah kompleksitas Kolmogorov.

Misalkan menunjukkan kompleksitas Kolmogorov dari sebuah string . Apakah ada string sedemikian rupa sehingga . (Di sini adalah gabungan dengan dirinya sendiri). Pertanyaan serupa tetapi berbeda diajukan $K(x)$ $x$ $K(xx)<K(x)$ $xx$ $x$ sini , tetapi contoh tandingan yang diberikan dalam jawaban atas pertanyaan itu tidak berhasil untuk pertanyaan ini.

cc.complexity-theory kolmogorov-complexity Sune Jakobsen
sumber

Jawaban:

Saya bukan ahli dalam kompleksitas Kolmogorov, tetapi saya berpikir bahwa x tersebut dapat dibangun untuk setiap fungsi kompleksitas K sebagai berikut. Karena 1, 11, 1111, 11111111, ..., 1 ^{2 ⁿ} , ... adalah pengkodean dari bilangan alami n , K (1 ^{2 ⁿ} ) tidak boleh o (log n ). Namun, ketika n = 2 ^m , jelas K (1 ^{2 ⁿ} ) = K (1 ^{2 ^{2 ^m}} ) = O (log m ) = O (log log n ). Oleh karena itu urutan K (1), K (11), K (1111), K (11111111),…, K (1 ^{2 ⁿ} ), ... tidak dapat secara lemah meningkat secara monoton, yang berarti bahwa terdapat string x dalam bentuk 1 ^{2 ⁿ} sedemikian rupa sehingga K ( xx ) <K ( x ).

Tsuyoshi Ito
sumber

@ Tsuyoshi, Apakah ada string yang tidak dapat dimampatkan

sehingga

x

$x$

K (x x) < K (x)

$K(xx)\lt K(x)$

Mohammad Al-Turkistany

Saya berpikir bahwa

dan K (1 ^ {2 ^ n}) = Ω (log n) saling bertentangan. Maksudnya adalah: Jika

maka

K (1^{2^{2^{m}}}) = O (\log m)

$K(1^{2^{2^m}})=O(\log m)$

f (n) = o (\log n)

$f(n)=o(\log n)$

. Kalau tidak, buktinya tampak baik-baik saja.

K (1^{2^{n}}) \neq O (f (n))

$K(1^{2^n})\neq O(f(n))$

Sune Jakobsen

Ini sepertinya berhasil. Memang, saya pikir itu memberi Anda urutan tak terbatas dari string seperti itu. Namun, entah saya salah mengerti sesuatu, atau pernyataan aturan rantai untuk Kompleksitas Kolmogorov yang muncul di wikipedia ( en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity ) kemudian salah. Awalnya saya berpikir bahwa definisi wikipedia mungkin tidak berlaku di sini, karena di sana Anda harus dapat mengetahui di mana X end dan Y mulai, sementara di sini ini tampaknya tidak diperlukan, tetapi ketika Y = X Anda dapat menambahkannya ke deskripsi di O (1) dengan mengatakan "split in the middle".

Abel Molina

@Sune: Notasi Ω (⋅) memiliki beberapa definisi yang sedikit berbeda. “K (1 ^ 2 ^ n) = Ω (log n)” dalam jawaban saya berarti “limsup K (1 ^ 2 ^ n) / log n> 0,” dan itu tidak bertentangan dengan “K (1 ^ 2 ^ 2 ^ m) = O (log m). ”Saya mengedit jawaban untuk menjelaskan hal ini. Lihat juga Definisi laju pertumbuhan asimptotik apa yang harus kita ajarkan?

Tsuyoshi Ito

@turkistany dan semua: Perhatikan bahwa selalu benar bahwa K (xx)> K (x) -c untuk beberapa konstanta, saya pikir ini harus ditunjukkan. Ini juga berarti bahwa kita memerlukan definisi yang sangat tepat tentang yang tidak dapat dimampatkan jika kita ingin mempelajari pertanyaan ini. Saya kira jawabannya lagi ya, tapi saya tidak punya bukti.

domotorp

Iya. Kompleksitas Kolomogorov dalam praktiknya bergantung pada model Anda. Mesin Turing, program Java, program C ++, ... jika ada keanehan pada model Anda yang memungkinkan hal ini terjadi pada set input yang terbatas, itu tidak masalah.

Pertanyaan yang lebih baik adalah seberapa banyak perilaku ini dapat Anda hindari dan masih memiliki model yang universal.

Chad Brewbaker
sumber

Saya pikir pertanyaan yang lebih baik adalah: Apakah x seperti itu ada untuk semua model? Saya tidak tahu apa "model" secara formal, tetapi tampaknya jawaban Tsuyoshi bekerja untuk semua bahasa pemrograman yang masuk akal.

Sune Jakobsen

0

$0$

x x

$xx$

x

$x$

@ Tsuyoshi:

Saya tidak mengerti dengan baik bukti Anda.

$K(s)$ $s$ atasnya.

$TM_{ss}$ $ss = 1111...1 = 1^{2^{n+1}}$ $TM_{s}$ $s = 1^{2^n}$

Bisakah bukti Anda diterapkan pada kompleksitas Kolmogorov di TM?

$n+1 = 2^{m}$ $TM_{ss}$ $TM_{s}$ $n$ ) ... Terima kasih!

(maaf, tapi saya tidak tahu bagaimana memposting ini sebagai komentar)

Marzio De Biasi
sumber

Untuk menulis komentar pada posting yang dibuat oleh orang lain selain Anda yang bukan jawaban untuk pertanyaan Anda, Anda memerlukan poin reputasi setidaknya 50.

Tsuyoshi Ito