Clase EXPTIME
La clase de complejidad EXPTIME (a veces llamada simplemente EXP) es un conjunto de problemas, en la teoría de la complejidad computacional, que puede resolver una máquina de Turing determinista en tiempo O (2 p ( n ) ), donde p(n) es una función polinomial de n.
Propiedades
Se sabe que
P NP PSPACE EXPTIME NEXPTIME EXPSPACE
Además, por el teorema de la jerarquía en:tiempo y el teorema de la jerarquía en:espacio
P TIEMPO EXPERTO ; NP PRÓXIMO TIEMPO; ESPACIO EXP ESPACIO
Véase también
Literatura
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M. : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .
| Clases de complejidad de algoritmos | |
|---|---|
| Considerado ligero |
|
| Se supone que es difícil | |
| Considerado difícil |
|