Złożoność Kołmogorowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Złożoność Kołmogorowa – dla łańcucha symboli, skończonego lub nieskończonego, to długość najkrótszego programu, który generuje dany łańcuch. Nazwa pojęcia pochodzi od nazwiska Andrieja Kołmogorowa.

Rozwinięcie dziesiętne liczby pi, choć nieskończone, ma bardzo niską złożoność Kołmogorowa, ponieważ istnieje bardzo prosty program, który generuje dowolną liczbę jej cyfr. Złożoność Kołmogorowa jest różna dla różnych komputerów (ściślej – maszyn Turinga lub obiektów izomorficznych z nimi). Ze względu na problem stopu nie może istnieć algorytm obliczający złożoność Kołmogorowa z gwarancją sukcesu.