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.
Je známo že
P NP PSPACE EXPTIME NEXPTIME EXPSPACETaké pomocí teorému o hierarchii en:času a teorému o hierarchii en:prostoru
P EXPTIME ; NP NEXPTIME ; PSPACE EXPSPACETřídy složitosti algoritmů | |
---|---|
Považováno za světlo | |
Prý to bude těžké | |
Považováno za obtížné |
|