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
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .
| Třídy složitosti algoritmů | |
|---|---|
| Považováno za světlo | |
| Prý to bude těžké | |
| Považováno za obtížné |
|