Jaka jest złożoność algorytmiczna?

Złożoność algorytmiczna, (złożoność obliczeniowa lub złożoność Kolmogorowa), jest podstawową ideą zarówno w teorii złożoności obliczeniowej , jak i teorii informacji algorytmicznej i odgrywa ważną rolę w formalnej indukcji.

Algorytmiczna złożoność łańcucha binarnego jest definiowana jako najkrótszy i najbardziej wydajny program, który może wytwarzać ciąg.Chociaż istnieje nieskończona liczba programów, które mogą tworzyć dowolny ciąg, jeden program lub grupa programów zawsze będzie najkrótsza.Nie ma algorytmicznego sposobu znalezienia najkrótszego algorytmu, który wyświetla dany ciąg;Jest to jeden z pierwszych wyników teorii złożoności obliczeniowej.Mimo to możemy zgadywać.Wynik ten, (złożoność obliczeniowa łańcucha) okazuje się bardzo ważna dla dowodów związanych z obliczeniami.

Ponieważ każdy obiekt fizyczny lub właściwość można zasadniczo opisać z bliskim wyczerpaniem przez ciąg bitów, obiektów i właściwościMożna powiedzieć, że ma również złożoność algorytmiczną.W rzeczywistości zmniejszenie złożoności obiektów w świecie rzeczywistym do programów, które wytwarzają obiekty jako wynik, jest jednym ze sposobów oglądania przedsiębiorstwa nauki.Złożone obiekty wokół nas zwykle pochodzą z trzech głównych procesów generujących;

Pojawienie się , ewolucja i Inteligencja , z obiektami wytwarzanymi przez każde złożone w kierunku większej złożoności algorytmicznej.

Złożoność obliczeniowa jest pojęciem często stosowanym w informatyce teoretycznej w celu ustalenia względnej trudności w obliczeniu roztworów na szerokoklasistych klasachproblemów matematycznych i logicznych.Istnieje ponad 400 klas złożoności i stale odkrywane są dodatkowe klasy.Słynne pytanie

p ' np dotyczy charakteru dwóch z tych klas złożoności.Zajęcia złożoności obejmują problemy o wiele trudniejsze niż cokolwiek, można by się skonfrontować w matematyce do rachunku różniczkowego.Istnieje wiele możliwych problemów w teorii złożoności obliczeniowej, które wymagałyby niemal infinity czasu do rozwiązania.

Złożoność algorytmiczna i powiązane koncepcje zostały opracowane w latach 60. XX wieku przez dziesiątki badaczy.Andrey Kolmogorov, Ray Solomonoff i Gregory Chaitin wnieśli ważny wkład pod koniec lat 60. z algorytmiczną teorią informacji.Zasada minimalnej długości wiadomości, ściśle związana ze złożonością algorytmiczną, stanowi znaczną część wnioskowania statystycznego i indukcyjnego oraz uczenia maszynowego.