NTIME

En 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 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 va a 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 a la que se puede acceder.

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:

${\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 dice que las máquinas no deterministas pueden resolver más problemas en asintóticamente más tiempo.

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))}$.

Referencias

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