Co je to Algoritmická složitost?
Algoritmická složitost (výpočetní složitost nebo Kolmogorovova složitost) je základní myšlenkou jak v teorii výpočetní složitosti, tak v teorii algoritmické informace 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ý může řetězec produkovat. Přestože existuje nekonečný počet programů, které mohou produkovat 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 udělat vzdělaný odhad. Tento výsledek (výpočetní složitost řetězce) se ukazuje jako velmi důležitý pro důkazy související s vypočítatelností.
Protože jakýkoli fyzický objekt nebo vlastnost lze v zásadě popsat téměř vyčerpáním řetězcem bitů, lze také říci, že objekty a vlastnosti mají algoritmickou složitost. Ve skutečnosti je snížení složitosti skutečných objektů na programy, které tyto objekty produkují jako výstup, jedním ze způsobů, jak zobrazit podnik vědy. Složité objekty kolem nás mají tendenci pocházet ze tří hlavních generačních procesů; vznik , evoluce a inteligence , s objekty vytvořenými každým sklonem k větší algoritmické složitosti.
Výpočetní složitost je pojem, který se často používá v teoretické informatice k určení relativní obtížnosti výpočtu řešení pro velké třídy 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á otázka P = NP se týká povahy dvou z těchto tříd složitosti. Třídy složitosti zahrnují problémy mnohem obtížnější, než cokoli, s čím by se matematici mohli potýkat, až po počet. V teorii výpočetní složitosti je mnoho představitelných problémů, které by vyžadovaly řešení téměř nekonečného času.
Algoritmická složitost a související koncepce byly vyvinuty v 60. letech desítkami vědců. Andrey Kolmogorov, Ray Solomonoff a Gregory Chaitin významně přispěli koncem 60. let pomocí teorie algoritmických informací. Princip minimální délky zprávy, úzce související s algoritmickou složitostí, poskytuje velkou část základů statistického a indukčního odvozování a strojového učení.