Hispanopedia Wiki
Articulo de referencia

DLIN

En la teoría de la complejidad computacional , DLIN es la clase de problemas de decisión que pueden ser resueltos por una máquina de Turing multitape en tiempo lineal, O ( n ). ...

Hispanopedia WikiContenido en espanolLectura gratuita

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