En la teoría de la complejidad computacional , la clase de complejidad NTIME ( f ( n )) es el conjunto de problemas de decisión que puede resolver una máquina de Turing no determinista que se ejecuta en el tiempo O ( f ( n )). Aquí O es la notación O grande , f es alguna función y n es el tamaño de la entrada (para la cual se decidirá el problema).
Significado
Esto significa que hay una máquina no determinista que, para una entrada dada de tamaño n , se ejecutará en el 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. De manera equivalente, existe una máquina de Turing determinista M que se ejecuta en el 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.
Limitaciones de espacio
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 accesible.
Relación con otras clases de complejidad
La conocida clase de complejidad NP se puede definir en términos de NTIME de la siguiente manera:
Del mismo modo, la clase NEXP se define en términos de NTIME:
El teorema de la jerarquía de tiempo no determinista dice que las máquinas no deterministas pueden resolver más problemas en más tiempo asintóticamente.
NTIME también está relacionado con DSPACE de la siguiente manera. Para cualquier función construible de tiempo t ( n ), tenemos
- .
Una generalización de NTIME es ATIME , definida con máquinas de Turing alternas . Resulta que
- .