Artikel ini membutuhkan perhatian dari ahli subjek terkait. Harap tambahkan alasan atau pranala ke halaman pembicaraan untuk menjelaskan masalah pada artikel tersebut. Jika Anda adalah ahli yang dapat membantu, silakan perbaiki kualitas artikel ini.
Gambar ini menggambarkan bagian fraktalhimpunan Mandelbrot. Cukup dengan menyimpan warna 24-bit setiap piksel pada gambar ini akan membutuhkan 1,62 juta bit, tetapi sebuah program komputer kecil dapat mereproduksi 1,62 juta bit ini dengan menggunakan definisi himpunan Mandelbrot dan koordinat sudut gambar. Dengan demikian, kompleksitas Kolmogorov dari berkas mentah yang mengkodekan bitmap ini kurang dari 1,62 juta bit dalam model komputasi pragmatis mana pun.
Dalam teori informasi algoritmik (subbidang dari ilmu komputer dan matematika), Kompleksitas Kolmogorov dari sebuah objek (misalnya sepotong teks), adalah panjang dari program komputer terpendek (dalam bahasa pemrograman yang telah ditentukan) yang menghasilkan objek sebagai keluaran. Kompleksitas ini adalah ukuran dari perhitungan sumber daya yang dibutuhkan untuk menentukan objek, dan juga dikenal sebagai kompleksitas deskriptif Kolmogorov - Chaitin, entropi algoritmik, atau kompleksitas ukuran program. Istilah ini dinamai sesuai Andrey Kolmogorov, yang pertama kali menerbitkan tulisan terkait subjek ini pada tahun 1963.[1][2]
Gagasan tentang kompleksitas Kolmogorov dapat digunakan untuk menyatakan dan membuktikan kemustahilan sama dengan argumen diagonal Cantor, Teorema ketidaklengkapan Gödel, dan masalah terputus Turing. Secara khusus, tidak ada satu pun program P yang bisa menghitung batas bawah untuk setiap kompleksitas Kolmogorov teks yang dapat mengembalikan nilai yang pada dasarnya lebih besar dari panjang P sendiri; karenanya tidak ada satu program pun yang dapat menghitung kompleksitas Kolmogorov secara tepat untuk banyak teks yang tak terhingga.
