Clasa EXPTIME
Clasa de complexitate EXPTIME (uneori numită pur și simplu EXP) este un set de probleme, în teoria complexității computaționale, care poate fi rezolvată de o mașină Turing deterministă în timp O (2 p ( n ) ), unde p(n) este o funcție polinomială din n.
Proprietăți
Se știe că
P NP PSPACE EXPTIME NEXPTIME EXPSPACE
De asemenea, prin teorema en:time hierarchy și en:space hierarchy teorema
P EXPTIME ; NP NEXPTIME ; PSPACE EXPSPACE
Vezi și
Literatură
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M . : „Williams” , 2002. - 528 p. - ISBN 0-201-44124-1 .
| Clasele de complexitate ale algoritmilor | |
|---|---|
| Considerată ușoară | |
| Ar trebui să fie dificil | |
| Considerat dificil |
|