Menggunakan kompleksitas Kolmogorov sebagai input “ukuran”

Katakanlah kita memiliki masalah komputasi, misalnya 3-SAT, yang memiliki seperangkat contoh masalah (mungkin input) . Biasanya dalam analisis algoritma atau teori kompleksitas komputasi, kami memiliki beberapa set dari semua input dengan panjang , dan fungsi yang memberikan waktu berjalan beberapa algoritma solusi pada input . Urutan waktu berjalan terburuk untuk kemudian I ( n ) = { w ∈ S : | w | = n } n T ( w ) A w A f n = maks w ∈ I ( n ) T ( w ) $S$

$$I(n) = \{w \in S : |w| = n\}$$ $n$$T(w)$$A$$w$$A$ $$f_n = \max_{w \in I(n)} T(w).$$

Sekarang mari kita mendefinisikan set

$$I^K(n) = \{w \in S : K(w) = n \}$$ dari semua input dengan kompleksitas Kolmogorov $n$ , dan mari kita mendefinisikan urutan $$f^K_n = \frac{1}{\left|I^K(n)\right|} \sum_{w \in I^K(n)} T(w).$$ Di sini $f^K$ adalah urutan waktu berjalan rata-rata untuk $A$ , kecuali jika "ukuran" input adalah kompleksitas Kolmogorov mereka, bukan panjangnya.

Apakah ada algoritma yang $f_n$ secara asimtotik berbeda nyata dari $f^K_n$ ? Jika demikian, apakah ada masalah yang kompleksitas waktunya berubah ketika menggunakan cara analisis algoritma yang berbeda ini?

Pertimbangkan fungsi paritas (atau fungsi lain yang bergantung pada semua / sebagian bit input). Untuk fungsi paritas, . Jadi Di sisi lain, f n = Θ ( n ) . f K n = Θ ( $T(w) = \Theta(|w|)$

$$f_n = \Theta(n).$$ $$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$

Perhatikan bahwa . Dengan demikian dan . Demikian pula, ; dengan demikian “tumbuh sangat cepat”. Selain itu, tidak sulit untuk melihat bahwa tidak ada dihitung atas menuju .maks w : K ( w ) = n | w | ≥ 2 2 Ω ( n ) f K n ≥ 2 2 Ω ( n ) / 2 n → ∞ K ( 2 … 2 2 n ) = O ( n ) f K $K(2^{2^n}) = O(n)$

$$\max_{w:K(w) = n} |w| \geq 2^{2^{\Omega(n)}}$$ $f_n^K \geq 2^{2^{\Omega(n)}} / 2^n \to \infty$$K(2^{\dots^{2^{2^n}}}) = O(n)$f K $f_n^K \geq 2^{\dots^{2^{2^{\Omega(n)}}}}/2^n$$f_n^K$

Mengingat minat pada pertanyaan ini, saya pikir mungkin akan membantu untuk menunjukkan secara lebih eksplisit alasan mengapa kita tidak perlu terkejut sama sekali dengan jawaban itu dan mencoba memberikan arahan untuk penyempurnaan pertanyaan. Ini mengumpulkan dan memperluas beberapa komentar. Saya minta maaf jika ini "jelas"!

Pertimbangkan sekumpulan string kompleksitas Kolmogorov : Paling banyak ada string seperti itu, karena ada deskripsi panjang . Tetapi perhatikan bahwa set ini tidak dapat ditentukan untuk umum (jika tidak, kita dapat menghitung hanya dengan mengulangi dari ke dan memeriksa keanggotaan dalam ). Selanjutnya, fungsi tumbuh sangat cepat. Ini adalah varian dari fungsi sibuk-berang-berang: apa output terpanjang oleh Mesin Turing dengan panjang deskripsi$n$

$$J^K(n) = \{w : K(w) = n\}.$$ $2^n$$2^n$$n$$n$$K(w)$$n=1$$|w|$$J^K(n)$ $$g^K(n) = \max_{w \in J^K(n)} |w|$$ $n$? Jika ini tumbuh lebih lambat dari beberapa fungsi yang dapat dihitung, kita dapat memutuskan masalah penghentian: Diberikan TM , bangun yang mensimulasikan dan mencetak pada setiap langkah. Jika panjang deskripsi adalah , maka: berhenti paling banyak pada langkah ; atau tidak berhenti.$M$$M'$$M$$1$$M'$$n$$M$$g^K(n)$$M$

Sekarang, untuk pertanyaan Andrew, kita memiliki , di mana adalah bahasa aslinya. Jadi satu-satunya cara untuk menghindari mengandung input sangat besar dalam adalah jika hanya berisi string yang sangat tidak dapat dikompresi. (Perhatikan bahwa, jika tidak, kita dapat sepenuhnya mengabaikan perbedaan antara kasus terburuk dan analisis kasus rata-rata di sini, karena kita rata-rata lebih dari string, tetapi ukuran string terbesar tumbuh lebih cepat daripada fungsi komputabel . )$I^K(n) = S \cap J^K(n)$$S$$I^K(n)$$n$$S$$2^n$$n$

Saya merasa bahwa ada kemungkinan tidak mungkin untuk membangun setiap trivial (yaitu tak terbatas) yang hanya berisi string uncompressible, namun adalah decidable. Tapi saya tidak tahu. Namun, mudah-mudahan ini memberikan intuisi mengapa kita tidak harus berharap untuk kebanyakan bahasa memiliki tumbuh lebih lambat dari fungsi komputasi.$S$$f^K_n$

Untuk mundur sedikit, pertanyaannya adalah membandingkan kinerja pada input panjang ke kinerja pada input yang dapat dikompresi dengan panjang . Tetapi kami memiliki gagasan kompresi yang jauh lebih mudah ditelusuri (dan kurang kuat) daripada Kompleksitas Kolmogorov. Sebuah cara sederhana adalah dengan memberikan rangkaian ukuran , yang pada input nomor biner menghasilkan th sedikit . Perhatikan bahwa di sini blowup dalam ukuran input paling banyak bersifat eksponensial (rangkaian ukuran memiliki paling banyak input yang mungkin).$n$$n$$n$$b$$b$$w$$n$$2^n$

Jadi kita dapat mengulangi pertanyaan dengan membiarkan Dan mendefinisikan analog. Alasan untuk harapan di sini adalah bahwa sebagian besar string memerlukan rangkaian yang hampir sebesar string itu sendiri, dan tidak ada string yang lebih besar daripada rangkaian yang dibutuhkan secara eksponensial. Mungkin dalam kasus ini kita bisa menemukan bahasa di mana dan mirip tanpa .

$$I^C(n) = \{ w \in S : \text{the smallest circuit implicitly specifying $w$ has size $n$}\}.$$ $f^C_n$$f_n$$f^C_n$

Pertanyaan yang cukup dekat hubungannya adalah kompleksitas bahasa implisit seperti IMPLICIT_SAT adalah lengkap-NEXP, dan biasanya versi implisit masalah NP-lengkap adalah NEXP-lengkap. Memutuskan IMPLICIT_SAT setidaknya semudah hanya menggunakan sirkuit untuk menuliskan semua , lalu menjalankan algoritme untuk SAT pada . Jadi jika untuk SAT, maka ini sepertinya dekat dengan memberikan bukti bahwa IMPLICIT_SAT dalam kasus rata-rata hampir secepat dapat ditentukan seperti SAT dalam kasus terburuk. Tapi saya tidak tahu bagaimana orang akan secara langsung membandingkan gagasan Anda dengan bahasa implisit karena gagasan "sirkuit terkecil untukw w f C n = Θ ( f n )

$$\mathsf{IMPLICIT\_SAT} = \{ \text{circuits $C$}: \text{$C$ implicitly specifies $w$}, w \in \mathsf{SAT}\}.$$ $w$$w$$f^C_n = \Theta(f_n)$$w$"tidak ikut bermain untuk bahasa implisit.

Semoga ini bermanfaat / menarik!

Saya tidak yakin dengan buku teks yang menyebutkan masalah implisit, tetapi di sini ada beberapa catatan kuliah: http://people.seas.harvard.edu/~salil/cs221/spring10/lec8.pdf

$S$$S$$L$$n$$2^n-n$$f^K_{n}$$2^{f_n}$