Třída EXPTIME

Třída složitosti EXPTIME (někdy nazývaná jednoduše EXP) je soubor problémů v teorii výpočetní složitosti, které lze vyřešit deterministickým Turingovým strojem v čase O (2 p ( n ) ), kde p(n) je polynomiální funkce. z n.

Vlastnosti

Je známo že

P NP PSPACE EXPTIME NEXPTIME EXPSPACE

Také pomocí teorému o hierarchii en:času a teorému o hierarchii en:prostoru

P EXPTIME ; NP NEXPTIME ; PSPACE EXPSPACE

Viz také

Literatura