Jaka jest złożoność algorytmiczna?
Złożoność algorytmiczna (złożoność obliczeniowa lub złożoność Kołmogorowa), jest podstawową ideą zarówno w teorii złożoności obliczeniowej i teorii informacji algorytmicznej i odgrywa ważną rolę w indukcji formalnej.
Złożoność algorytmiczna ł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ć. Ten wynik (złożoność obliczeniowa łańcucha) okazuje się bardzo ważna dla dowodów związanych z obliczeniami.
, ponieważ dowolny obiekt fizyczny lub właściwość można zasadniczo opisać z prawie ekspresją przez ciąg bitów, obiekty i właściwości mogą być S.Pomoc w złożoności algorytmicznej. 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; Emergence , 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 rozwiązań szerokich klas problemów matematycznych i logicznych. Istnieje ponad 400 klas złożoności i stale odkrywane są dodatkowe klasy. Słynne p = np pytanie dotyczy natury dwóch z tych klas złożoności. Zajęcia złożoności obejmują problemy znacznie trudniejsze niż cokolwiekmoże skonfrontować się z matematyką 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 naukowców. 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.