EXPTIME osztály
Az EXPTIME komplexitási osztály (néha egyszerűen EXP-nek is nevezik) a számítási komplexitáselméletben olyan problémák halmaza, amelyeket egy determinisztikus Turing-gép O (2 p ( n ) ) idő alatt megoldhat , ahol p(n) egy polinomiális függvény. n.
Tulajdonságok
Ismeretes, hogy
P NP PSPACE EXPTIME NEXPTIME EXPSPACE
Továbbá az en:time hierarchia tétel és az en:space hierarchia tétel alapján
P EXPTIME ; NP NEXPTIME ; PSPACE EXPSPACE
Lásd még
Irodalom
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba. - M . : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .
| Algoritmusok összetettségi osztályai | |
|---|---|
| Fénynek tekinthető | |
| Állítólag nehéz | |
| Nehéznek tartott |
|