Diferencia entre revisiones de «NTIME»
Ir a la navegación
Ir a la búsqueda
imported>Alelapenya m Desambiguando enlaces a NP (enlace cambiado a NP (clase de complejidad)) con DisamAssist. |
(Sin diferencias)
|
Revisión actual - 21:50 14 sep 2020
En teoría de la complejidad computacional, la clase de complejidad NTIME(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en tiempo O(f(n)) y espacio ilimitado.
La clase de complejidad NP se puede definir en términos de NTIME como: