NTIME

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:

$\mbox{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k)$