Hispanopedia Wiki
Articulo de referencia

NLIN

En la teoría de la complejidad computacional , NLIN es la clase de problemas de decisión que pueden ser resueltos por una máquina de Turing multitape no determinista en tiempo l...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la complejidad computacional , NLIN es la clase de problemas de decisión que pueden ser resueltos por una máquina de Turing multitape no determinista en tiempo lineal, O ( n ). Se sabe que esta clase difiere de su contraparte determinista, DLIN . [ 1 ]

Referencias

  1. ↑ Balcázar, José Luis; Díaz, Josep; Gabarro, Joaquim (1990). Complejidad Estructural II . Springer Verlag. ISBN 3-540-52079-1., Teorema 3.9