Apa itu kompleksitas algoritmik?

Kompleksitas algoritmik, (kompleksitas komputasi, atau kompleksitas Kolmogorov), adalah ide mendasar dalam teori kompleksitas komputasi dan teori informasi algoritmik , dan memainkan peran penting dalam induksi formal.

Kompleksitas algoritmik dari string biner didefinisikan sebagai program terpendek dan paling efisien yang dapat menghasilkan string.Meskipun ada sejumlah program yang tak terbatas yang dapat menghasilkan string yang diberikan, satu program atau kelompok program akan selalu menjadi yang terpendek.Tidak ada cara algoritmik untuk menemukan algoritma terpendek yang menghasilkan string yang diberikan;Ini adalah salah satu hasil pertama dari teori kompleksitas komputasi.Meski begitu, kita bisa membuat tebakan yang berpendidikan.Hasil ini, (kompleksitas komputasi suatu string), ternyata sangat penting untuk bukti yang terkait dengan komputasi.

Karena setiap objek atau properti fisik pada prinsipnya dapat dijelaskan agar hampir habis dengan serangkaian bit, objek dan propertiDapat dikatakan memiliki kompleksitas algoritmik juga.Faktanya, mengurangi kompleksitas objek dunia nyata menjadi program yang menghasilkan objek sebagai output, adalah salah satu cara untuk melihat perusahaan sains.Benda -benda kompleks di sekitar kita cenderung berasal dari tiga proses pembangkit utama; Munculnya , Evolusi , dan Kecerdasan , dengan objek yang dihasilkan oleh masing -masing cenderung ke arah kompleksitas algoritmik yang lebih besar.masalah matematika dan logis.Ada lebih dari 400 kelas kompleksitas, dan kelas tambahan terus ditemukan.Pertanyaan

p ' np

yang terkenal menyangkut sifat dari dua kelas kompleksitas ini.Kelas kompleksitas termasuk masalah yang jauh lebih sulit daripada apa pun yang mungkin dihadapi dalam matematika hingga kalkulus.Ada banyak masalah yang dapat dibayangkan dalam teori kompleksitas komputasi yang akan membutuhkan waktu yang hampir tak terbatas untuk dipecahkan. Kompleksitas algoritmik dan konsep terkait dikembangkan pada 1960-an oleh lusinan peneliti.Andrey Kolmogorov, Ray Solomonoff dan Gregory Chaitin memberikan kontribusi penting di akhir 60 -an dengan teori informasi algoritmik.Prinsip panjang pesan minimum, terkait erat dengan kompleksitas algoritmik, memberikan banyak dasar inferensi statistik dan induktif dan pembelajaran mesin.