Co je algoritmická složitost?
Algoritmická složitost (výpočetní složitost nebo Kolmogorovova složitost) je základní myšlenkou v teorii Teorie výpočetní složitosti a Algoritmic Information Theory a hraje důležitou roli ve formální indukci.
Algoritmická složitost binárního řetězce je definována jako nejkratší a nejúčinnější program, který dokáže vytvořit řetězec. Přestože existuje nekonečný počet programů, které mohou vytvořit jakýkoli daný řetězec, jeden program nebo skupina programů bude vždy nejkratší. Neexistuje žádný algoritmický způsob, jak najít nejkratší algoritmus, který vydává daný řetězec; Toto je jeden z prvních výsledků teorie výpočetní složitosti. Přesto můžeme učinit vzdělaný odhad. Tento výsledek (výpočetní složitost řetězce) se ukáže jako velmi důležitý pro důkazy týkající se výpočetního.Pomoc mít také algoritmickou složitost. Ve skutečnosti je snížení složitosti reálných objektů na programy, které produkují objekty jako výstup, jedním ze způsobů, jak prohlížet podnik vědy. Složité objekty kolem nás mají tendenci pocházet ze tří hlavních generovacích procesů; vznik , evoluce a inteligence , s objekty produkovanými každým sklonem k větší algoritmické složitosti.
Výpočetní složitost je představa, která se často používá v teoretické informatice k určení relativní obtížnosti výpočtu řešení širokých tříd matematických a logických problémů. Existuje více než 400 tříd složitosti a neustále se objevují další třídy. Slavná p = np otázka se týká povahy dvou z těchto tříd složitosti. Třídy složitosti zahrnují problémy mnohem obtížnější než jinýmůže se konfrontovat v matematice až do počtu. Existuje mnoho představitelných problémů v teorii výpočetní složitosti, které by vyžadovaly řešení téměř nekonečného času.
Algoritmická složitost a související koncepty byly vyvinuty v 60. letech desítkami vědců. Andrey Kolmogorov, Ray Solomonoff a Gregory Chaitin na konci 60. let významně přispěli algoritmickou informační teorií. Princip minimální délky zprávy, úzce související s algoritmickou složitostí, poskytuje velkou část základů statistického a induktivního inference a strojového učení.