En la teoría de la complejidad computacional , la clase de complejidad NTIME( f ( n )) es el conjunto de problemas de decisión que pueden resolverse mediante una máquina de Turing no determinista que se ejecuta en un tiempo O ( f ( n )). Aquí O es la notación O mayúscula , f es alguna función y n es el tamaño de la entrada (para la cual se debe decidir el problema).
Esto significa que hay una máquina no determinista que, para una entrada dada de tamaño n , se ejecutará en tiempo O ( f ( n )) (es decir, dentro de un múltiplo constante de f ( n ), para n mayor que algún valor), y siempre "rechazará" la entrada si la respuesta al problema de decisión es "no" para esa entrada, mientras que si la respuesta es "sí", la máquina "aceptará" esa entrada para al menos una ruta de cálculo. Equivalentemente, hay una máquina de Turing determinista M que se ejecuta en tiempo O ( f ( n )) y es capaz de verificar un certificado de longitud O ( f ( n )) para una entrada; si la entrada es una instancia "sí", entonces se acepta al menos un certificado, si la entrada es una instancia "no", ningún certificado puede hacer que la máquina acepte.
El espacio disponible para la máquina no está limitado, aunque no puede exceder O ( f ( n )), porque el tiempo disponible limita la cantidad de cinta a la que se puede acceder.
La conocida clase de complejidad NP se puede definir en términos de NTIME de la siguiente manera:
De manera similar, la clase NEXP se define en términos de NTIME:
El teorema de jerarquía temporal no determinista dice que las máquinas no deterministas pueden resolver más problemas en un tiempo asintóticamente mayor.
NTIME también está relacionado con DSPACE de la siguiente manera. Para cualquier función construible en el tiempo t ( n ), tenemos
Una generalización de NTIME es ATIME , definida con máquinas de Turing alternadas . Resulta que
Zoológico de complejidad : NTIME(f(n)).
