Cobhamova teze - Cobham's thesis

Nesmí být zaměňována s Cobhamovou větou .

Cobhamova práce , známá také jako Cobham – Edmondsova práce (pojmenovaná po Alanu Cobhamovi a Jacku Edmondsovi ), tvrdí, že výpočetní problémy lze na nějakém výpočetním zařízení proveditelně provést, pouze pokud je lze vypočítat v polynomiálním čase ; to znamená, že v případě, že leží ve složitosti třídy P . V moderních termínech, identifikuje povolný problémy se složitostí třídy P .

Formálně říci, že problém lze vyřešit v polynomiálním čase, znamená říci, že existuje algoritmus, který vzhledem k n -bitové instanci problému jako vstupu může produkovat řešení v čase O ( n c ), písmeno O je notace velkého O a c je konstanta, která závisí na problému, ale ne na konkrétní instanci problému.

Dokument Alana Cobhama z roku 1965 s názvem „Vnitřní výpočetní obtížnost funkcí“ je jednou z prvních zmínek o konceptu třídy složitosti P , který se skládá z problémů, o nichž lze rozhodnout v polynomiálním čase. Cobham se domníval, že tato třída složitosti je dobrým způsobem, jak popsat soubor proveditelně vyčíslitelných problémů.

Papír Jacka Edmondse z roku 1965 „Cesty, stromy a květiny“ je také připočítán s identifikací P s problémy, které je možné řešit.

Omezení

Graf ukazuje čas řešení problému v milisekundách (ms) vs. velikost problému, n, pro problémy s batohem vyřešené nejmodernějším specializovaným algoritmem pomocí počítače Pentium III s frekvencí 933 MHz (průměr 100 instancí, data z :). Vhodnost kvadratické rovnice naznačuje, že empirická algoritmická složitost pro instance s 50–10 000 proměnnými je O ((log  n ) 2 ), přestože teoreticky má exponenciální odhad složitosti nejhoršího případu.

Zatímco Cobhamova práce je důležitým mezníkem ve vývoji teorie výpočetní složitosti , má omezení, pokud jde o praktickou proveditelnost algoritmů. Tato práce v podstatě uvádí, že „ P “ znamená „snadné, rychlé a praktické“, zatímco „ne v P “ znamená „tvrdé, pomalé a nepraktické“. To ale není vždy pravda, protože práce abstrahuje některé důležité proměnné, které v praxi ovlivňují dobu běhu:

  • Ignoruje konstantní faktory a podmínky nižšího řádu.
  • Ignoruje velikost exponentu. Čas hierarchie teorém dokazuje, že existují problémy v P vyžadujících libovolně velké exponenty.
  • Ignoruje typickou velikost vstupu.

Všechny tři jsou příbuzné a jsou obecnými stížnostmi na analýzu algoritmů , ale vztahují se zejména na Cobhamovu tezi, protože výslovně tvrdí o praktičnosti. Podle Cobhamovy práce je problém, pro který nejlepší algoritmus bere n 200 instrukcí, považován za proveditelný a problém s algoritmem, který vyžaduje 2 0,00001 n instrukcí, neproveditelný - i když jeden by nikdy nemohl vyřešit instanci velikosti n = 2 s předchozím algoritmem , vzhledem k tomu, instanci posledně uvedeného problému velikosti n = 10 6 by mohl být vyřešen bez obtíží. V oblastech, kde praktické problémy mají miliony proměnných (například Operační výzkum nebo Automatizace elektronického designu ), jsou dokonce algoritmy O ( n 3 ) často nepraktické.

Reference