Algoritmik karmaşıklık (hesaplama karmaşıklığı veya Kolmogorov karmaşıklığı), hem hesaplama karmaşıklığı teorisi hem de algoritmik bilgi teorisinde temel bir fikirdir ve formal indüksiyonda önemli bir rol oynar.
İkili bir dizgenin algoritmik karmaşıklığı dizgeyi üretebilecek en kısa ve en verimli program olarak tanımlanır. Herhangi bir dizgiyi üretebilecek sonsuz sayıda program olmasına rağmen, bir program veya program grubu her zaman en kısa olacaktır. Verilen bir dizgeyi çıkaran en kısa algoritmayı bulmanın algoritmik bir yolu yoktur; bu hesaplama karmaşıklığı teorisinin ilk sonuçlarından biridir. Yine de eğitimli bir tahmin yapabiliriz. Bu sonuç, (bir dizgenin hesap karmaşıklığı), hesaplanabilirlikle ilgili ispatlar için çok önemli olduğu ortaya çıktı.
Herhangi bir fiziksel nesne veya özellik prensipte prensip olarak bir bit dizisi tarafından bitkinliğe açıklanabileceği için, nesneler ve özelliklerin de algoritmik karmaşıklığa sahip olduğu söylenebilir. Aslında, gerçek dünyadaki nesnelerin karmaşıklığını, nesneleri çıktı olarak üreten programlara indirgemek, bilim kurumunu görmenin bir yoludur. Çevremizdeki karmaşık nesneler üç ana üretim sürecinden gelme eğilimindedir; ortaya çıkması , evrimi ve zekası , her biri tarafından üretilen nesnelerle daha fazla algoritmik karmaşıklığa yöneliyor.
Hesaplamalı karmaşıklık, teorik bilgisayar bilimlerinde, çözümleri geniş matematiksel ve mantıksal problem sınıflarına hesaplamanın zorluğunu belirlemek için sıkça kullanılan bir kavramdır. 400'den fazla karmaşıklık sınıfı vardır ve ek sınıflar sürekli olarak keşfedilmektedir. Ünlü P = NP sorunu, bu karmaşıklık sınıfının ikisinin doğası ile ilgilidir. Karmaşıklık sınıfları matematikte matematikten karşısına çıkan her şeyden çok daha zor olan problemleri içerir. Hesaplamalı karmaşıklık teorisinde çözmek için sınırsız miktarda zaman gerektiren hayal edilebilir birçok sorun vardır.
Algoritmik karmaşıklık ve ilgili kavramlar, 1960'larda onlarca araştırmacı tarafından geliştirilmiştir. Andrey Kolmogorov, Ray Solomonoff ve Gregory Chaitin, 60'ların sonunda algoritmik bilgi teorisi ile önemli katkılarda bulundu. Algoritmik karmaşıklıkla yakından ilişkili minimum mesaj uzunluğu ilkesi, istatistiksel ve endüktif çıkarım ve makine öğrenmesinin temelini sağlar.
