Kombinatorická exploze

Kombinatorická exploze je v matematice neformální označení jevu, kdy složitost daného problému silně vzrůstá spolu s tím, jak se vzhledem k rostoucímu vstupu velice rychle rozšiřuje kombinatorické jádro problému, typicky počet kombinací, které by mohly být řešením.

Příklady

Počet latinských čtverců

Latinský čtverec je čtvercová síť $n\times n$, do které jsou vepsána přirozená čísla od 1 do $n$ takovým způsobem, že každé číslo je v každém řádku i sloupci právě jednou. Počet různých latinských čtverců pro rostoucí $n$ roste velice rychle:

n	Počet latinských čtverců velikosti n
1	1
2	2
3	12
4	576
5	161 280
6	812 851 200
7	61 479 419 904 000
8	108 776 032 459 082 956 800
9	5 524 751 496 156 892 842 531 225 600
10	9 982 437 658 213 039 871 725 064 756 920 320 000
11	776 966 836 171 770 144 107 444 346 734 230 682 311 065 600 000

Šachy

Šachy nejsou vyřešená hra, tedy není známá optimální strategie ani pro jednoho hráče, která by zaručeně vedla k vítězství. Problémem je právě velikost stavového prostoru. V roce 2005 se povedlo dopočítat všechny koncovky s nejvýše šesti kameny, dalších deset let trvalo, než se podařilo dopočítat všechny koncovky s nejvýše sedmi kameny a výsledná databáze má velikost 140 terabajtů.

Reference

V tomto článku byl použit překlad textu z článku Combinatorial explosion na anglické Wikipedii.