NTIME

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 ser resueltos por una máquina de Turing no determinista que se ejecuta en tiempo O ( f ( n )), donde 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 debe decidir el problema).

Esto significa que hay una máquina no determinista que, para una entrada dada de tamaño n , se ejecutará, para todas las rutas de cálculo, en tiempo O ( f ( n )) (es decir, dentro de un múltiplo constante fijo 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, 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 que se puede alcanzar.

La conocida clase de complejidad NP se puede definir en términos de NTIME de la siguiente manera:

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})}$

De manera similar, la clase NEXP se define en términos de NTIME:

${\displaystyle {\mathsf {NEXP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$

El teorema de la jerarquía temporal no determinista establece 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

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$.

Una generalización de NTIME es ATIME , definida con máquinas de Turing alternas . Resulta que

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {ATIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$.

Zoológico de complejidad : NTIME( f ( n )) .